Performance evaluation of distributed maximum weighted matching algorithms

Can Umut Ileri, Orhan Dagdeviren

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

6 Citations (Scopus)

Abstract

Graph matching is a fundamental graph theory problem which has a broad application range including information retrieval, pattern recognition, graph partitioning, chemical structure analysis, protein function prediction, backup placement and cellular coverage. This problem has gained attention in distributed computing as there are distributed matching algorithms with asymptotically guaranteed time bounds and approximation ratios. On the other side, we do not know the practical performance of these algorithms. In this paper, we provide a detailed performance evaluation of asynchronous distributed maximum weighted matching (MWM) algorithms. We assume a message-passing system in CONGEST model in which the message size is limited to O(log n) where n is the number of nodes. This model is popular for energy-efficient networks such as wireless sensor networks. We used a discrete event simulator, SimPy, to model the assumed network structures. We provide the implementations of Watthenhofer and Wattenhofer's algorithm, Hoepman's algorithm, Lotker et al.'s algorithm and Lotker et al.'s improvement algorithm. The results show that the greedy algorithm of Hoepman performed best in approximating the optimum result in all types of networks, even achieving an approximation ratio of 0.99 in some instances. To the best of our knowledge this is the first study which provides an extensive performance evaluation of distributed MWM algorithms.

Original languageEnglish
Title of host publication2016 6th International Conference on Digital Information and Communication Technology and Its Applications, DICTAP 2016
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages103-108
Number of pages6
ISBN (Electronic)9781467396097
DOIs
Publication statusPublished - 15 Aug 2016
Externally publishedYes
Event6th International Conference on Digital Information and Communication Technology and Its Applications, DICTAP 2016 - Konya, Turkey
Duration: 21 Jul 201623 Jul 2016

Conference

Conference6th International Conference on Digital Information and Communication Technology and Its Applications, DICTAP 2016
CountryTurkey
CityKonya
Period21/07/1623/07/16

Keywords

  • Distributed Computing
  • Graph Matching
  • Performance Evaluation

Fingerprint Dive into the research topics of 'Performance evaluation of distributed maximum weighted matching algorithms'. Together they form a unique fingerprint.

Cite this