Moderately exponential time algorithms for the maximum induced matching problem
DOI10.1007/S11590-014-0813-ZzbMATH Open1327.90350OpenAlexW2026369499MaRDI QIDQ2355320FDOQ2355320
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
Recommendations
Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59)
Cites Work
- Exact exponential algorithms.
- Parameterized complexity of finding regular induced subgraphs
- Maximum \(k\)-regular induced subgraphs
- Induced matchings in subcubic planar graphs
- Maximum regular induced subgraphs in \(2P_3\)-free graphs
- Induced matchings
- On maximum induced matchings in bipartite graphs
- Induced matchings in asteroidal triple-free graphs
- The parameterized complexity of the induced matching problem
- Title not available (Why is that?)
- NP-completeness of some generalizations of the maximum matching problem
- 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
- New results on maximum induced matchings in bipartite graphs and beyond
- Algorithms for maximum independent sets
- Maximum \(r\)-regular induced subgraph problem: fast exponential algorithms and combinatorial bounds
- On the approximability of the maximum induced matching problem
- A parallel hybrid greedy branch and bound scheme for the maximum distance-2 matching problem
- Induced matchings in intersection graphs.
- Finding a maximum induced matching in weakly chordal graphs
- Bipartite Domination and Simultaneous Matroid Covers
- 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
- Improved induced matchings in sparse graphs
- On the induced matching problem
- Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
- Irredundant Set Faster Than O(2 n )
- Title not available (Why is that?)
- Title not available (Why is that?)
- Maximum induced matching problem on hhd-free graphs
Cited In (7)
- Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem
- Title not available (Why is that?)
- A bisection approach to subcubic maximum induced matching
- An improved exact algorithm for maximum induced matching
- Exact algorithms for maximum induced matching
- On the approximability of the maximum induced matching problem
- Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs
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)
