An improved kernel and parameterized algorithm for almost induced matching

DOI10.1007/978-981-97-2340-9_8MaRDI QIDQ6636070zbMATH OpenFDO

Authors Yuxi Liu, Mingyu Xiao

Publication date 12 November 2024

Full work available at URL https://doi.org/10.1007/978-981-97-2340-9_8

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Almost induced matching: linear kernels and parameterized algorithms
• 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 almost induced matching

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