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)

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

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)