An Improved Exact Algorithm for Maximum Induced Matching

DOI10.1007/978-3-319-17142-5_24zbMath1459.05318OpenAlexW2399274114MaRDI QIDQ2948473

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

graph algorithmsexact algorithmsmaximum induced matching

Mathematics Subject Classification ID

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

Related Items (5)

Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs ⋮ Almost Induced Matching: Linear Kernels and Parameterized Algorithms ⋮ Exact algorithms for maximum induced matching ⋮ Minimum number of maximal dissociation sets in trees ⋮ Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems

This page was built for publication: An Improved Exact Algorithm for Maximum Induced Matching