An improved kernel and parameterized algorithm for deletion to induced matching

DOI10.1016/J.TCS.2025.115215MaRDI QIDQ6988593zbMATH OpenFDO

Authors Yuxi Liu, Mingyu Xiao

Publication date 4 May 2025

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

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115215

zbMATH Keywords

graph algorithmsparameterized algorithmsmaximum induced matchinglinear kernel

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 2207482 (Why is no real title available?)
• A bisection approach to subcubic maximum induced matching
• Almost induced matching: linear kernels and parameterized algorithms
• 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.
• 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
• Graph-Theoretic Concepts in Computer Science
• Induced matchings
• Irredundancy in circular arc graphs
• Maximum r-regular induced subgraph problem: fast exponential algorithms and combinatorial bounds
• 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 algorithms and kernels for almost induced matching
• Parameterized complexity of finding regular induced subgraphs
• The parameterized complexity of the induced matching problem

This page was built for publication: An improved kernel and parameterized algorithm for deletion to induced matching

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