An improved exact algorithm for maximum induced matching

DOI10.1007/978-3-319-17142-5_24MaRDI QIDQ2948473zbMATH OpenOpenAlexFDO

Authors Mingyu Xiao, Huan Tan

Publication date 30 September 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-17142-5_24

zbMATH Keywords

exact algorithmsgraph algorithmsmaximum induced matching

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Exact algorithms for maximum induced matching
• Moderately exponential time algorithms for the maximum induced matching problem
• New results on induced matchings
• Exact algorithms for dominating induced matching based on graph partition
• scientific article; zbMATH DE number 1496857

Cited in

(17)

• Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs
• Improved induced matchings in sparse graphs
• Faster computation of the maximum dissociation set and minimum 3-path vertex cover in graphs
• Almost induced matching: linear kernels and parameterized algorithms
• A Faster Algorithm for Maximum Induced Matchings on Circle Graphs
• Parameterized algorithms and kernels for almost induced matching
• On the Induced Matching Problem
• Exact algorithms for maximum induced matching
• An improvement on Łuczak's connected matchings method
• The general maximum matching algorithm of Micali and Vazirani
• Minimum number of maximal dissociation sets in trees
• Moderately exponential time algorithms for the maximum induced matching problem
• The minimum number of maximal dissociation sets in unicyclic graphs
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• On the approximability of the maximum induced matching problem
• Exact algorithms for dominating induced matching based on graph partition
• Exact algorithms for minimum weighted dominating induced matching

This page was built for publication: An improved exact algorithm for maximum induced matching

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