Moderately exponential time algorithms for the maximum induced matching problem

DOI10.1007/S11590-014-0813-ZMaRDI QIDQ2355320zbMATH OpenOpenAlexFDO

Authors Maw-Shang Chang, Li-Hsuan Chen, Ling-Ju Hung

Publication date 22 July 2015

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11590-014-0813-z

zbMATH Keywords

approximation algorithminduced matchingmeasure and conquerbranch and reduce

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Exact algorithms for maximum induced matching
• An improved exact algorithm for maximum induced matching
• Publication:4944970
• Approximation and Online Algorithms
• New results on induced matchings

Cites work

• scientific article; zbMATH DE number 434499 (Why is no real title available?)
• scientific article; zbMATH DE number 9665 (Why is no real title available?)
• scientific article; zbMATH DE number 1496857 (Why is no real title available?)
• A parallel hybrid greedy branch and bound scheme for the maximum distance-2 matching problem
• Algorithms for maximum independent sets
• Approximability results for the maximum and minimum maximal induced matching problems
• Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
• Bipartite Domination and Simultaneous Matroid Covers
• Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
• Exact exponential algorithms.
• Finding a maximum induced matching in weakly chordal graphs
• 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
• Improved induced matchings in sparse graphs
• Induced matchings
• Induced matchings in asteroidal triple-free graphs
• Induced matchings in intersection graphs.
• Induced matchings in subcubic planar graphs
• Irredundant Set Faster Than O(2 n )
• Maximum \(k\)-regular induced subgraphs
• Maximum \(r\)-regular induced subgraph problem: fast exponential algorithms and combinatorial bounds
• Maximum induced matching problem on hhd-free graphs
• Maximum regular induced subgraphs in 2P₃-free graphs
• NP-completeness of some generalizations of the maximum matching problem
• New results on maximum induced matchings in bipartite graphs and beyond
• On maximum induced matchings in bipartite graphs
• On the approximability of the maximum induced matching problem
• On the induced matching problem
• Parameterized complexity of finding regular induced subgraphs
• The parameterized complexity of the induced matching problem

Cited in

(7)

• Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs
• Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem
• scientific article; zbMATH DE number 1496857 (Why is no real title available?)
• An improved exact algorithm for maximum induced matching
• A bisection approach to subcubic maximum induced matching
• Exact algorithms for maximum induced matching
• On the approximability of the maximum induced matching problem

This page was built for publication: Moderately exponential time algorithms for the maximum induced matching problem

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