Matchability and k-maximal matchings

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

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

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)

Cites Work

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

Cited In (9)

• Title not available (Why is that?)
• On vertex independence number of uniform hypergraphs
• Title not available (Why is that?)
• Factorially many maximum matchings close to the Erdős-Gallai bound
• Maximum matchings in the \(n\)-dimensional cube
• Title not available (Why is that?)
• Title not available (Why is that?)
• Rank-maximal matchings
• On maximum matchings in König-Egerváry graphs

   Recommendations

• Hardness and approximation of minimum maximal matchings 👍 👎
• On minimum maximal distance-\(k\) matchings 👍 👎
• Packing $k$-Matchings and $k$-Critical Graphs 👍 👎
• Title not available (Why is that?) 👍 👎
• Maximum Cardinality Simple 2-matchings in Subcubic Graphs 👍 👎

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)