Parameterized algorithms and kernels for almost induced matching

DOI10.1016/J.TCS.2020.09.026MaRDI QIDQ2210504zbMATH OpenOpenAlexFDO

Authors Mingyu Xiao, Shaowei Kou

Publication date 6 November 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2020.09.026

zbMATH Keywords

graph algorithmslinear kernelmaximum induced matchingparameterized algorithms

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Almost induced matching: linear kernels and parameterized algorithms
• The parameterized complexity of the induced matching problem
• Algorithms – ESA 2004
• Approximate parameterized matching
• Sublinear Algorithms for Parameterized Matching
• Exact algorithms for maximum induced matching
• An improved exact algorithm for maximum induced matching
• Parameterized and approximation algorithms for finding two disjoint matchings
• Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings
• Parameterized algorithms for inclusion of linear matchings

Cites work

• Almost induced matching: linear kernels and parameterized algorithms
• 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
• New results on induced matchings
• NP-completeness of some generalizations of the maximum matching problem
• 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

(12)

• Parameterized top-\(K\) algorithms
• Parameterized algorithms for inclusion of linear matchings
• Almost induced matching: linear kernels and parameterized algorithms
• A moment-matching Ferguson \& Klass algorithm
• Disconnected matchings
• Kernelization for edge triangle packing and covering via a discharging method
• A discharging method: improved kernels for edge triangle packing and covering
• An improved kernel and parameterized algorithm for almost induced matching
• Parameterized results on acyclic matchings with implications for related problems
• \(\mathcal{P}\)-matchings parameterized by treewidth
• An improved kernel and parameterized algorithm for deletion to induced matching
• Structural parameterizations for induced and acyclic matching

This page was built for publication: Parameterized algorithms and kernels for almost induced matching

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