Exact algorithms for maximum induced matching
From MaRDI portal
Publication:2407101
DOI10.1016/j.ic.2017.07.006zbMath1376.68070OpenAlexW2735767732MaRDI QIDQ2407101
Publication date: 28 September 2017
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2017.07.006
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (8)
Almost Induced Matching: Linear Kernels and Parameterized Algorithms ⋮ Attribute selection using contranominal scales ⋮ Computational complexity aspects of super domination ⋮ Exact Solution Algorithms for the Chordless Cycle Problem ⋮ Perfectly matched sets in graphs: parameterized and exact computation ⋮ Parameterized algorithms and kernels for almost induced matching ⋮ \textit{Branch} \& \textit{Memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees ⋮ Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs
Cites Work
- Unnamed Item
- Exact algorithms for dominating set
- A refined exact algorithm for edge dominating set
- Exact exponential algorithms.
- Irredundancy in circular arc graphs
- An exact algorithm for maximum independent set in degree-5 graphs
- Approximability results for the maximum and minimum maximal induced matching problems
- On the minimum feedback vertex set problem: Exact and enumeration algorithms
- 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
- Exact algorithms for edge domination
- New results on induced matchings
- Exact algorithms for maximum independent set
- An improved exact algorithm for undirected feedback vertex set
- A note on the complexity of minimum dominating set
- An Improved Exact Algorithm for Maximum Induced Matching
- A measure & conquer approach for the analysis of exact algorithms
- Algorithms for maximum independent sets
- Bipartite Domination and Simultaneous Matroid Covers
- 3-coloring in time
- Maximum $r$-Regular Induced Subgraph Problem: Fast Exponential Algorithms and Combinatorial Bounds
This page was built for publication: Exact algorithms for maximum induced matching
