Improved Induced Matchings in Sparse Graphs
From MaRDI portal
Publication:3656857
DOI10.1007/978-3-642-11269-0_11zbMath1273.68165OpenAlexW1553702732MaRDI QIDQ3656857
Matjaž Krnc, Rok Erman, Łukasz Kowalik, Tomasz Walen
Publication date: 14 January 2010
Published in: Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-11269-0_11
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- 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
- A linear 5-coloring algorithm of planar 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
This page was built for publication: Improved Induced Matchings in Sparse Graphs
