Almost induced matching: linear kernels and parameterized algorithms

DOI10.1007/978-3-662-53536-3_19MaRDI QIDQ3181060zbMATH OpenOpenAlexFDO

Authors Mingyu Xiao, Shaowei Kou

Publication date 22 December 2016

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-53536-3_19

zbMATH Keywords

graph algorithmsparameterized algorithmsmaximum induced matchinglinear kernel

Mathematics Subject Classification ID

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

Recommendations

• Parameterized algorithms and kernels for almost induced matching
• The parameterized complexity of the induced matching problem
• The Parameterized Complexity of the Induced Matching Problem in Planar Graphs
• Exact algorithms for maximum induced matching
• On the Induced Matching Problem

Cites work

• An improved exact algorithm for maximum induced matching
• An improved kernelization for \(P_{2}\)-packing
• Approximability results for the maximum and minimum maximal induced matching problems
• Bipartite Domination and Simultaneous Matroid Covers
• Editing graphs to satisfy degree constraints: a parameterized approach
• Exact algorithms for maximum induced matching
• Exact exponential algorithms.
• Faster Algebraic Algorithms for Path and Packing Problems
• 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
• Induced matchings
• Irredundancy in circular arc graphs
• Kernels for Packing and Covering Problems
• Looking at the stars
• Maximum r-regular induced subgraph problem: fast exponential algorithms and combinatorial bounds
• Minimum cost flows in graphs with unit capacities
• NP-completeness of some generalizations of the maximum matching problem
• New results on induced matchings
• On the approximability of the maximum induced matching problem
• On the induced matching problem
• Parameterized complexity of finding regular induced subgraphs
• The parameterized complexity of the induced matching problem

Cited in

(5)

• An improved kernel and parameterized algorithm for deletion to induced matching
• Parameterized algorithms and kernels for almost induced matching
• Parameterized algorithms for inclusion of linear matchings
• An improved kernel and parameterized algorithm for almost induced matching
• A moment-matching Ferguson \& Klass algorithm

This page was built for publication: Almost induced matching: linear kernels and parameterized algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3181060)