• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

A note on the hardness results for the labeled perfect matching problems in bipartite graphs

Monnot, Jérôme (2008), A note on the hardness results for the labeled perfect matching problems in bipartite graphs, RAIRO, 42, 3, p. 315-324. http://dx.doi.org/10.1051/ro:2008020

View/Open
Rairo_HardLM.pdf (144.1Kb)
Type
Article accepté pour publication ou publié
Date
2008
Journal name
RAIRO
Volume
42
Number
3
Publisher
EDP Sciences
Pages
315-324
Publication identifier
http://dx.doi.org/10.1051/ro:2008020
Metadata
Show full item record
Author(s)
Monnot, Jérôme cc
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 bounds

Related items

Showing items related by title and author.

  • Thumbnail
    A note on the hardness results for the labeled perfect matching problems in bipartite graphs 
    Monnot, Jérôme (2007) Document de travail / Working paper
  • Thumbnail
    The Labeled perfect matching in bipartite graphs 
    Monnot, Jérôme (2005) Article accepté pour publication ou publié
  • Thumbnail
    Approximation algorithms and hardness results for labeled connectivity problems 
    Hassin, Refael; Monnot, Jérôme; Segev, Danny (2007) Article accepté pour publication ou publié
  • Thumbnail
    Approximation Algorithms and Hardness Results for Labeled Connectivity Problems 
    Hassin, Refael; Monnot, Jérôme; Segev, Danny (2006) Communication / Conférence
  • Thumbnail
    On complexity and approximability of the Labeled maximum/perfect matching problems 
    Monnot, Jérôme (2005) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo