A note on the hardness results for the labeled perfect matching problems in bipartite graphs
RAIRO - Operations Research (2008)
- Volume: 42, Issue: 3, page 315-324
- ISSN: 0399-0559
Access Full Article
top
Abstract
topHow to cite
topMonnot, Jérôme. "A note on the hardness results for the labeled perfect matching problems in bipartite graphs." RAIRO - Operations Research 42.3 (2008): 315-324. <http://eudml.org/doc/250426>.
@article{Monnot2008,
abstract = {
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 Letters96 (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.
},
author = {Monnot, Jérôme},
journal = {RAIRO - Operations Research},
keywords = {Labeled matching; bipartite graphs; approximation
and complexity; inapproximation bounds.; labeled matching; approximation and complexity; inapproximation bounds},
language = {eng},
month = {8},
number = {3},
pages = {315-324},
publisher = {EDP Sciences},
title = {A note on the hardness results for the labeled perfect matching problems in bipartite graphs},
url = {http://eudml.org/doc/250426},
volume = {42},
year = {2008},
}
TY - JOUR
AU - Monnot, Jérôme
TI - A note on the hardness results for the labeled perfect matching problems in bipartite graphs
JO - RAIRO - Operations Research
DA - 2008/8//
PB - EDP Sciences
VL - 42
IS - 3
SP - 315
EP - 324
AB -
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 Letters96 (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.
LA - eng
KW - Labeled matching; bipartite graphs; approximation
and complexity; inapproximation bounds.; labeled matching; approximation and complexity; inapproximation bounds
UR - http://eudml.org/doc/250426
ER -
References
top- P. Alimonti and V. Kann, Hardness of approximating problems on cubic graphs, in Proc. CIAC'97, Lect. Notes Comput. Sci.1203 (1997) 288–298.
- S. Arora and M. Sudan, Improved low-degree testing and its applications. Combinatorica23 (2003) 365–426.
- K. Cameron, Coloured matchings in bipartite graphs. Discrete Math.169 (1997) 205–209.
- M. Costa, D. de Werra, C. Picouleau and B. Ries, Bicolored matchings in some classes of graphs. Graphs Comb.23 (2007) 47–60.
- A. Itai, M. Rodeh and S. Tanimoto, Some matching problems in bipartite graphs. J. ACM25 (1978) 517–525.
- J. Monnot, On Complexity and Approximability of the Labeled Maximum/Perfect Matching Problems, in Proc. ISAAC'05, Lect. Notes Comput. Sci.3827 (2005) 934–943.
- J. Monnot, The Labeled perfect matching in bipartite graphs. Inf. Proc. Lett.96 (2005) 81–88.
- A. Paz and S. Moran, Non deterministic polynomial optimisation problems and their approximation, Theor. Comput. Sci.95 (1981) 251–277.
- M.B. Richey and A.P. Punnen, Minimum Perfect Bipartite Matchings and Spanning Trees under Categorization. Discrete Appl. Math.39 (1992) 147–153.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.