On the induced matching problem

DOI10.1016/J.JCSS.2010.09.001MaRDI QIDQ657915zbMATH OpenOpenAlexFDO

Authors Iyad Kanj, Michael J. Pelsmajer, Marcus Schaefer, Ge Xia

Publication date 11 January 2012

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2008/1361/

zbMATH Keywords

induced matchingstwinless graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• On the Induced Matching Problem
• Improved induced matchings in sparse graphs
• Improved induced matchings in sparse graphs
• The parameterized complexity of the induced matching problem
• The Parameterized Complexity of the Induced Matching Problem in Planar Graphs

Cites work

• scientific article; zbMATH DE number 9665 (Why is no real title available?)
• scientific article; zbMATH DE number 1324671 (Why is no real title available?)
• scientific article; zbMATH DE number 1341905 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• scientific article; zbMATH DE number 1420901 (Why is no real title available?)
• Applications of a Planar Separator Theorem
• Large induced forests in triangle-free planar graphs
• Maximum induced linear forests in outerplanar graphs
• On the approximability of the maximum induced matching problem
• Parameterized complexity of finding regular induced subgraphs
• Problems and results in extremal combinatorics. I.
• The Parameterized Complexity of the Induced Matching Problem in Planar Graphs
• Tight bounds on maximal and maximum matchings

Cited in

(28)

• On the Induced Matching Problem
• The Parameterized Complexity of the Induced Matching Problem in Planar Graphs
• Exact algorithms for maximum induced matching
• Exploiting c-Closure in Kernelization Algorithms for Graph Problems
• Maximum matching in multi-interface networks
• Parameterized results on acyclic matchings with implications for related problems
• Essentially tight kernels for (weakly) closed graphs
• Parameterized complexity of perfectly matched sets
• On the approximability of the maximum induced matching problem
• A faster algorithm for maximum independent set on interval filament graphs
• Parameterized algorithms and kernels for almost induced matching
• Exploiting \(c\)-closure in kernelization algorithms for graph problems
• Bounding the mim‐width of hereditary graph classes
• Improved induced matchings in sparse graphs
• The parameterized complexity of the induced matching problem
• On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
• Almost induced matching: linear kernels and parameterized algorithms
• The minimum number of maximal independent sets in twin-free graphs
• Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem
• An improved kernel and parameterized algorithm for almost induced matching
• Maximum induced matching of hexagonal graphs
• On the Problem of Multiple Matching
• Perfectly matched sets in graphs: parameterized and exact computation
• Bounding the Mim-Width of Hereditary Graph Classes.
• A simple matching domain with indifferences and a master list
• Moderately exponential time algorithms for the maximum induced matching problem
• Induced packing of odd cycles in planar graphs
• New kernels for several problems on planar graphs

This page was built for publication: On the induced matching problem

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