Matchability and k-maximal matchings

DOI10.1016/J.DAM.2010.09.006zbMATH Open1203.05125OpenAlexW2103599375MaRDI QIDQ617892FDOQ617892

Authors Brian C. Dean, Stephen T. Hedetniemi, Jason Lewis, 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

treeschordal graphsbipartite graphsmaximal matchingsmatchabilityNP hardness

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) 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)

Recommendations

• Hardness and approximation of minimum maximal matchings
• On minimum maximal distance-\(k\) matchings
• Packing $k$-Matchings and $k$-Critical Graphs
• scientific article; zbMATH DE number 19225
• Maximum Cardinality Simple 2-matchings in Subcubic Graphs

Cites work

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

Cited in

(15)

• scientific article; zbMATH DE number 2081000 (Why is no real title available?)
• scientific article; zbMATH DE number 4114698 (Why is no real title available?)
• On maximum matchings in König-Egerváry graphs
• The maximum 1-2 matching problem and two kinds of its variants
• Recovery of disrupted airline operations using \(k\)-maximum matching in graphs
• Flexible Matchings
• On vertex independence number of uniform hypergraphs
• Factorially many maximum matchings close to the Erdős-Gallai bound
• scientific article; zbMATH DE number 19225 (Why is no real title available?)
• Maximum and optimal 1-2 matching problem of the different kind
• On upper bounds for parameters related to the construction of special maximum matchings
• Maximum matchings in the \(n\)-dimensional cube
• scientific article; zbMATH DE number 6469133 (Why is no real title available?)
• Rank-maximal matchings
• On minimum maximal distance-\(k\) matchings

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q617892)