Maximum induced matchings for chordal graphs in linear time

DOI10.1007/S00453-007-9045-2MaRDI QIDQ1018044zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

chordal graphslinear time algorithmlexicographic breadth-first searchmaximum induced matchingsperfect elimination order

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

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

Cites work

• scientific article; zbMATH DE number 434499 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 1496857 (Why is no real title available?)
• Algorithmic Aspects of Vertex Elimination on Graphs
• Bipartite Domination and Simultaneous Matroid Covers
• 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
• Induced matchings
• Induced matchings in asteroidal triple-free graphs
• Induced matchings in intersection graphs
• Irredundancy in circular arc graphs
• LexBFS-orderings and powers of chordal graphs
• NP-completeness of some generalizations of the maximum matching problem
• New results on induced matchings

Cited in

(22)

• Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs
• scientific article; zbMATH DE number 1496857 (Why is no real title available?)
• Connected matchings in chordal bipartite graphs
• A Faster Algorithm for Maximum Induced Matchings on Circle Graphs
• Graph classes and forbidden patterns on three vertices
• Maximum induced matching problem on hhd-free graphs
• Induced matchings in graphs of degree at most 4
• 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
• On distance-3 matchings and induced matchings
• Maximum induced matching algorithms via vertex ordering characterizations
• Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs
• On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs
• Well-indumatched pseudoforests
• 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
• Recent progress on strong edge-coloring of graphs
• Well-indumatched Trees and Graphs of Bounded Girth

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)