On the induced matching problem

DOI10.1016/j.jcss.2010.09.001zbMath1235.05114MaRDI 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 matchings; twinless graphs

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C10: Planar graphs; geometric and topological aspects of graph theory

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Related Items

Maximum matching in multi-interface networks, Maximum induced matching of hexagonal graphs, Induced packing of odd cycles in planar graphs, On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability, Parameterized algorithms and kernels for almost induced matching, New kernels for several problems on planar graphs, Moderately exponential time algorithms for the maximum induced matching problem, Almost Induced Matching: Linear Kernels and Parameterized Algorithms

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