On the induced matching problem

DOI10.1016/j.jcss.2010.09.001zbMath1235.05114OpenAlexW2059738021MaRDI QIDQ657915

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

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)

Related Items (max. 100)

Exploiting $c$-Closure in Kernelization Algorithms for Graph Problems ⋮ Almost Induced Matching: Linear Kernels and Parameterized Algorithms ⋮ A faster algorithm for maximum independent set on interval filament graphs ⋮ On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability ⋮ Maximum matching in multi-interface networks ⋮ Parameterized complexity of perfectly matched sets ⋮ Bounding the mim‐width of hereditary graph classes ⋮ Essentially tight kernels for (weakly) closed graphs ⋮ Perfectly matched sets in graphs: parameterized and exact computation ⋮ 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. ⋮ Maximum induced matching of hexagonal graphs ⋮ New kernels for several problems on planar graphs ⋮ Induced packing of odd cycles in planar graphs ⋮ Moderately exponential time algorithms for the maximum induced matching problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized complexity of finding regular induced subgraphs
• Problems and results in extremal combinatorics. I.
• On the approximability of the maximum induced matching problem
• Tight bounds on maximal and maximum matchings
• Maximum induced linear forests in outerplanar graphs
• Large induced forests in triangle-free planar graphs
• The Parameterized Complexity of the Induced Matching Problem in Planar Graphs
• Applications of a Planar Separator Theorem

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