Improved induced matchings in sparse graphs

DOI10.1016/j.dam.2010.08.026zbMath1215.05129OpenAlexW2151566751MaRDI QIDQ608287

Łukasz Kowalik, Rok Erman, Matjaž Krnc, Tomasz Walen

Publication date: 25 November 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2010.08.026

zbMATH Keywords

planar graphsinduced matchingsparse graphsFPT algorithm

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Exploiting $c$-Closure in Kernelization Algorithms for Graph Problems ⋮ Induced matchings in subcubic graphs without short cycles ⋮ Parameterized complexity of perfectly matched sets ⋮ Essentially tight kernels for (weakly) closed graphs ⋮ Towards optimal kernel for connected vertex cover in planar graphs ⋮ Perfectly matched sets in graphs: parameterized and exact computation ⋮ Exploiting c-Closure in Kernelization Algorithms for Graph Problems ⋮ New kernels for several problems on planar graphs ⋮ Moderately exponential time algorithms for the maximum induced matching problem

Cites Work

• Parameterized complexity of finding regular induced subgraphs
• The parameterized complexity of the induced matching problem
• Lower bounds on the cardinality of the maximum matchings of planar graphs
• NP-completeness of some generalizations of the maximum matching problem
• Call routing and the ratcatcher
• On the approximability of the maximum induced matching problem
• Tight bounds on maximal and maximum matchings
• Large induced forests in sparse graphs
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Efficient Approximation Schemes for Maximization Problems onK3,3-free orK5-free Graphs
• On the Induced Matching Problem
• Node-and edge-deletion NP-complete problems
• Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures
• Decomposition of Finite Graphs Into Forests
• Unnamed Item

This page was built for publication: Improved induced matchings in sparse graphs