Matchability and \(k\)-maximal matchings

DOI10.1016/j.dam.2010.09.006zbMath1203.05125OpenAlexW2103599375MaRDI QIDQ617892

Jason Lewis, Stephen T. Hedetniemi, Brian C. Dean, Alice A. McRae, Sandra M. Hedetniemi

Publication date: 14 January 2011

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2010.09.006

zbMATH Keywords

bipartite graphstreeschordal graphsmaximal matchingsmatchabilityNP hardness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

On vertex independence number of uniform hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The perfectly matchable subgraph polytope of an arbitrary graph
• Gallai theorems for graphs, hypergraphs, and set systems
• Matching theory
• On generalised minimal domination parameters for paths
• Approximating matchings in parallel
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• A separation algorithm for the matchable set polytope
• Regularity and locality in \(k\)-terminal graphs
• Linear-time computation of optimal subgraphs of decomposable graphs
• Approximate Max-Flow on Small Depth Networks
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Matchability and \(k\)-maximal matchings