| Issue |
RAIRO-Oper. Res.
Volume 42, Number 3, July-September 2008
|
|
|---|---|---|
| Page(s) | 315 - 324 | |
| DOI | https://doi.org/10.1051/ro:2008020 | |
| Published online | 20 August 2008 | |
A note on the hardness results for the labeled perfect matching problems in bipartite graphs
CNRS LAMSADE, Université
Paris-Dauphine, Place du Maréchal De Lattre de Tassigny, 75775
Paris Cedex 16, France; monnot@lamsade.dauphine.fr
Received:
3
March
2006
Accepted:
29
October
2007
In this note, we strengthen the inapproximation bound of O(logn) 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.
Mathematics Subject Classification: 68Q17 / 68R10 / 68W25 / 90C59
Key words: Labeled matching / bipartite graphs / approximation and complexity / inapproximation bounds.
© EDP Sciences, ROADEF, SMAI, 2008
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.