A bisection approach to subcubic maximum induced matching

DOI10.1007/978-981-97-0566-5_19MaRDI QIDQ6575400zbMATH OpenFDO

Authors Gordon Hoi, Sanjay Jain, Ammar Fathin Sabili, Frank Stephan

Publication date 19 July 2024

Full work available at URL https://doi.org/10.1007/978-981-97-0566-5_19

zbMATH Keywords

branch and boundexponential time algorithmsfixed parameter tractable problemsgraph theorymeasure and conquer

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A measure \& conquer approach for the analysis of exact algorithms
• Bipartite Domination and Simultaneous Matroid Covers
• Exact algorithms for maximum independent set
• Exact algorithms for maximum induced matching
• Exact exponential algorithms.
• 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
• Induced matchings
• Irredundancy in circular arc graphs
• Maximum r-regular induced subgraph problem: fast exponential algorithms and combinatorial bounds
• Moderately exponential time algorithms for the maximum induced matching problem
• New methods for 3-SAT decision and worst-case analysis
• New results on induced matchings
• NP-completeness of some generalizations of the maximum matching problem
• On the approximability of the maximum induced matching problem
• Pathwidth of cubic graphs and exact algorithms
• Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets
• Upper bounds on the bisection width of 3- and 4-regular graphs

Cited in

(1)

• An improved kernel and parameterized algorithm for deletion to induced matching

This page was built for publication: A bisection approach to subcubic maximum induced matching

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