Maximum induced matchings for chordal graphs in linear time
From MaRDI portal
Publication:1018044
DOI10.1007/S00453-007-9045-2zbMATH Open1171.68595OpenAlexW1999576733MaRDI QIDQ1018044FDOQ1018044
Authors: Andreas Brandstädt, Chính T. Hoàng 
Publication date: 13 May 2009
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-007-9045-2
Recommendations
- Finding a maximum induced matching in weakly chordal graphs
- Maximum induced matchings in graphs
- Maximum vertex-weighted matching in strongly chordal graphs
- Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs
- On maximum induced matchings in bipartite graphs
- Approximation and Online Algorithms
- Induced matchings in graphs of bounded maximum degree
- Maximum induced matching algorithms via vertex ordering characterizations
- Maximum induced matching algorithms via vertex ordering characterizations
- A Faster Algorithm for Maximum Induced Matchings on Circle Graphs
chordal graphslinear time algorithmlexicographic breadth-first searchmaximum induced matchingsperfect elimination order
Cites Work
- Title not available (Why is that?)
- Induced matchings
- Algorithmic Aspects of Vertex Elimination on Graphs
- Induced matchings in asteroidal triple-free graphs
- 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 induced matchings
- Finding a maximum induced matching in weakly chordal graphs
- Bipartite Domination and Simultaneous Matroid Covers
- Induced matchings in intersection graphs
- LexBFS-orderings and powers of chordal graphs
- Irredundancy in circular arc graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (22)
- Title not available (Why is that?)
- Connected matchings in chordal bipartite graphs
- A Faster Algorithm for Maximum Induced Matchings on Circle Graphs
- Graph classes and forbidden patterns on three vertices
- Induced matchings in graphs of degree at most 4
- Maximum induced matching problem on hhd-free graphs
- A min-max property of chordal bipartite graphs with applications
- Graphs with maximal induced matchings of the same size
- Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs
- Induced matchings in strongly biconvex graphs and some algebraic applications
- On distance-3 matchings and induced matchings
- Edge open packing: complexity, algorithmic aspects, and bounds
- Maximum induced matching algorithms via vertex ordering characterizations
- Maximum induced matching algorithms via vertex ordering characterizations
- On distance-3 matchings and induced matchings
- On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs
- Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs
- Well-indumatched pseudoforests
- Recent progress on strong edge-coloring of 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
- Well-indumatched Trees and Graphs of Bounded Girth
- Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs
This page was built for publication: Maximum induced matchings for chordal graphs in linear time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1018044)
