The parameterized complexity of the induced matching problem
type: Item
instance of: scholarly article
title: The parameterized complexity of the induced matching problem
zbMATH Open document ID: 1172.05350
author: Hannes Moser
author: Somnath Sikdar
published in: Discrete Applied Mathematics
publication date: 2009-06-30T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5572553
zbMATH Keywords: induced matching
zbMATH Keywords: parameterized complexity
zbMATH Keywords: planar graph
zbMATH Keywords: kernelization
zbMATH Keywords: tree decomposition
MaRDI profile type: Publication
full work available at URL: j.dam.2008.07.011
OpenAlex ID: W2095912437
cites work: Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
cites work: SOFSEM 2006: Theory and Practice of Computer Science
cites work: Polynomial-time data reduction for dominating set
cites work: Q3044360
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: Q4699283
cites work: Treewidth: Characterizations, Applications, and Computations
cites work: Induced matchings
cites work: Induced matchings in intersection graphs.
cites work: Finding a maximum induced matching in weakly chordal graphs
cites work: Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
cites work: Algorithms – ESA 2004
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: The complexity of irredundant sets parameterized by size
cites work: Q4393480
cites work: On the approximability of the maximum induced matching problem
cites work: Claw-free graphs---a survey
cites work: The Lost Continent of Polynomial Time: Preprocessing and Kernelization
cites work: Parametrized complexity theory.
cites work: Automata, Languages and Programming
cites work: Q3139292
cites work: Irredundancy in circular arc graphs
cites work: New results on induced matchings
cites work: Approximation and Online Algorithms
cites work: Linear Problem Kernels for NP-Hard Problems on Planar Graphs
cites work: Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual
cites work: On the Induced Matching Problem
cites work: Treewidth. Computations and approximations
cites work: Divide-and-Color
cites work: Bipartite Domination and Simultaneous Matroid Covers
cites work: Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
cites work: On maximum induced matchings in bipartite graphs
cites work: Some results on graphs without long induced paths
cites work: Q5710169
cites work: Approximability results for the maximum and minimum maximal induced matching problems
cites work: Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
cites work: A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
cites work: NP-completeness of some generalizations of the maximum matching problem
cites work: A Parameterized Perspective on Packing Paths of Length Two
cites work: Q4944970
DOI: 10.1016/J.DAM.2008.07.011
description: scientific article; zbMATH DE number 5572553