The labeled perfect matching in bipartite graphs

DOI10.1016/j.ipl.2005.06.009zbMath1191.68470OpenAlexW2090200648MaRDI QIDQ1044711

Jérôme Monnot

Publication date: 18 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://basepub.dauphine.fr/handle/123456789/2949

zbMATH Keywords

bipartite graphsNP-completeapproximate algorithmslabeled matching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (21)

Traveling salesman problems in temporal graphs ⋮ The label cut problem with respect to path length and label frequency ⋮ An Introduction to Temporal Graphs: An Algorithmic Perspective ⋮ Graph matching problems and the NP-hardness of sortedness constraints ⋮ Secluded connectivity problems ⋮ Minimum <scp>color‐degree</scp> perfect b‐matchings ⋮ The Complexity of Bottleneck Labeled Graph Problems ⋮ Approximation and hardness results for label cut and related problems ⋮ Simpler and better approximation algorithms for the unweighted minimum label \(s\)-\(t\) cut problem ⋮ Labeled traveling salesman problems: complexity and approximation ⋮ The parameterized complexity of some minimum label problems ⋮ Minimum label \(s\)-\(t\) cut has large integrality gaps ⋮ Bi-criteria and approximation algorithms for restricted matchings ⋮ A note on the clustered set covering problem ⋮ On complexity of special maximum matchings constructing ⋮ The maximum labeled path problem ⋮ A note on the hardness results for the labeled perfect matching problems in bipartite graphs ⋮ The complexity of bottleneck labeled graph problems ⋮ The labeled maximum matching problem ⋮ Maximum cuts in edge-colored graphs ⋮ An Introduction to Temporal Graphs: An Algorithmic Perspective^*

Cites Work

• Optimization, approximation, and complexity classes
• On approximation algorithms for the minimum satisfiability problem
• Coloured matchings in bipartite graphs
• Some APX-completeness results for cubic graphs
• The minimum labeling spanning trees
• On the minimum label spanning tree problem
• Matchings in colored bipartite networks
• Local search for the minimum label spanning tree problem with bounded color classes.
• A note on the minimum label spanning tree.
• Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem
• Improved Approximation Algorithms for MAX SAT
• A threshold of ln n for approximating set cover
• Some Matching Problems for Bipartite Graphs
• Spanning trees with many or few colors in edge-colored graphs
• Bicolored matchings in some classes of graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The labeled perfect matching in bipartite graphs