Parameterized algorithms and kernels for almost induced matching

DOI10.1016/j.tcs.2020.09.026zbMath1464.68300OpenAlexW3087503125MaRDI QIDQ2210504

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 algorithmsparameterized algorithmsmaximum induced matchinglinear kernel

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) 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)

Related Items (1)

Disconnected matchings

Cites Work

• Unnamed Item
• Editing graphs to satisfy degree constraints: a parameterized approach
• Exact exponential algorithms.
• On the induced matching problem
• Irredundancy in circular arc graphs
• Looking at the stars
• Approximability results for the maximum and minimum maximal induced matching problems
• An improved kernelization for \(P_{2}\)-packing
• Parameterized complexity of finding regular induced subgraphs
• The parameterized complexity of the induced matching problem
• NP-completeness of some generalizations of the maximum matching problem
• Induced matchings
• 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
• On the approximability of the maximum induced matching problem
• New results on induced matchings
• Exact algorithms for maximum induced matching
• Kernels for Packing and Covering Problems
• Almost Induced Matching: Linear Kernels and Parameterized Algorithms
• Faster Algebraic Algorithms for Path and Packing Problems
• Bipartite Domination and Simultaneous Matroid Covers
• Maximum $r$-Regular Induced Subgraph Problem: Fast Exponential Algorithms and Combinatorial Bounds
• Maximal Induced Matchings in Triangle-Free Graphs

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