Parameterized algorithms and kernels for almost induced matching
From MaRDI portal
Publication:2210504
DOI10.1016/j.tcs.2020.09.026zbMath1464.68300OpenAlexW3087503125MaRDI QIDQ2210504
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
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)
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
