The Parameterized Complexity of the Induced Matching Problem in Planar Graphs

DOI10.1007/978-3-540-73814-5_32zbMath1214.05128OpenAlexW2134710838MaRDI QIDQ3612599

Hannes Moser, Somnath Sikdar

Publication date: 10 March 2009

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-73814-5_32

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

A Retrospective on (Meta) Kernelization ⋮ On the induced matching problem ⋮ Maximum induced matching algorithms via vertex ordering characterizations ⋮ A linear kernel for a planar connected dominating set ⋮ Linear kernelizations for restricted 3-Hitting Set problems ⋮ Maximum induced matching of hexagonal graphs ⋮ Bidimensionality and Kernels ⋮ On the induced matching problem in Hamiltonian bipartite graphs ⋮ Maximum Induced Matching Algorithms via Vertex Ordering Characterizations

This page was built for publication: The Parameterized Complexity of the Induced Matching Problem in Planar Graphs