A note on the hardness results for the labeled perfect matching problems in bipartite graphs
From MaRDI portal
Publication:3598040
DOI10.1051/ro:2008020zbMath1157.68053MaRDI QIDQ3598040
Publication date: 29 January 2009
Published in: RAIRO - Operations Research (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/105405
68R10: Graph theory (including graph drawing) in computer science
90C59: Approximation methods and heuristics in mathematical programming
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
Related Items
Cites Work
- The labeled perfect matching in bipartite graphs
- Non deterministic polynomial optimization problems and their approximations
- Minimum perfect bipartite matchings and spanning trees under categorization
- Coloured matchings in bipartite graphs
- Improved low-degree testing and its applications
- Some Matching Problems for Bipartite Graphs
- Algorithms and Computation
- Bicolored matchings in some classes of graphs
