Maximum induced matchings close to maximum matchings

DOI10.1016/j.tcs.2015.04.001zbMath1326.05120OpenAlexW1969438192MaRDI QIDQ2348267

Uéverton S. Souza, Dieter Rautenbach, Felix Joos, Lucia Draque Penso, Marcio Antônio Duarte

Publication date: 11 June 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.04.001

zbMATH Keywords

fixed parameter tractabilityinduced matchingstrong matching

Mathematics Subject Classification ID

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

Related Items (7)

Perfect matching cuts partitioning a graph into complementary subgraphs ⋮ On the hardness of deciding the equality of the induced and the uniquely restricted matching number ⋮ Degenerate matchings and edge colorings ⋮ Approximating weighted induced matchings ⋮ Maximum matchings of a digraph based on the largest geometric multiplicity ⋮ On some hard and some tractable cases of the maximum acyclic matching problem ⋮ Equality of distance packing numbers

Cites Work

• Unnamed Item
• Parameterized complexity of finding regular induced subgraphs
• The parameterized complexity of the induced matching problem
• Matching theory
• NP-completeness of some generalizations of the maximum matching problem
• Induced matchings
• Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
• New results on maximum induced matchings in bipartite graphs and beyond
• The graphs with maximum induced matching and maximum matching the same size

This page was built for publication: Maximum induced matchings close to maximum matchings