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

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

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 (15)

• 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
• Flexible Matchings
• Title not available (Why is that?)
• Title not available (Why is that?)
• Rank-maximal matchings
• On maximum matchings in König-Egerváry graphs
• Recovery of disrupted airline operations using \(k\)-maximum matching in graphs
• Maximum and optimal 1-2 matching problem of the different kind
• On upper bounds for parameters related to the construction of special maximum matchings
• On minimum maximal distance-\(k\) matchings
• The maximum 1-2 matching problem and two kinds of its variants

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)