
A note on the hardness results for the labeled perfect matching problems in bipartite graphs
Monnot, Jérôme (2007), A note on the hardness results for the labeled perfect matching problems in bipartite graphs. https://basepub.dauphine.fr/handle/123456789/20749
View/ Open
Type
Document de travail / Working paperDate
2007Series title
Cahier du LAMSADESeries number
256Published in
Paris
Metadata
Show full item recordAuthor(s)
Monnot, Jérôme
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
In this note, we strengthen the inapproximation bound of O(log n) for the labeled perfect matching problem established in J. Monnot, The Labeled perfect matching in bipartite graphs, Information Processing Letters 96 (2005) 81-88, using a self improving operation in some hard instances. It is interesting to note that this self improving operation does not work for all instances. Moreover, based on this approach we deduce that the problem does not admit constant approximation algorithms for connected planar cubic bipartite graphs.Subjects / Keywords
labeled matching; bipartite graphs; Approximation and complexity; inapproximation boundsRelated items
Showing items related by title and author.
-
Monnot, Jérôme (2008) Article accepté pour publication ou publié
-
Monnot, Jérôme (2005) Article accepté pour publication ou publié
-
Hassin, Refael; Monnot, Jérôme; Segev, Danny (2007) Article accepté pour publication ou publié
-
Hassin, Refael; Monnot, Jérôme; Segev, Danny (2006) Communication / Conférence
-
Monnot, Jérôme (2005) Communication / Conférence