Exact algorithms for maximum induced matching

DOI10.1016/j.ic.2017.07.006zbMath1376.68070OpenAlexW2735767732MaRDI QIDQ2407101

Mingyu Xiao, Huan Tan

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

zbMATH Keywords

graph algorithmsexact algorithmsmaximum induced matching

Mathematics Subject Classification ID

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

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