Maximum induced matchings for chordal graphs in linear time

DOI10.1007/s00453-007-9045-2zbMath1171.68595OpenAlexW1999576733MaRDI QIDQ1018044

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

linear time algorithmchordal graphsperfect elimination orderlexicographic breadth-first searchmaximum induced matchings

Mathematics Subject Classification ID

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

Related Items

Graphs with maximal induced matchings of the same size ⋮ Induced matchings in strongly biconvex graphs and some algebraic applications ⋮ A min-max property of chordal bipartite graphs with applications ⋮ Well-indumatched Trees and Graphs of Bounded Girth ⋮ Maximum induced matching algorithms via vertex ordering characterizations ⋮ On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs ⋮ Induced Matchings in Graphs of Degree at Most 4 ⋮ On distance-3 matchings and induced matchings ⋮ Maximum induced matching problem on hhd-free graphs ⋮ On Distance-3 Matchings and Induced Matchings ⋮ Recent progress on strong edge-coloring of graphs ⋮ Graph Classes and Forbidden Patterns on Three Vertices ⋮ Connected matchings in chordal bipartite graphs ⋮ Maximum Induced Matching Algorithms via Vertex Ordering Characterizations ⋮ Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs ⋮ Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs

Cites Work

• Irredundancy in circular arc graphs
• NP-completeness of some generalizations of the maximum matching problem
• Induced matchings
• LexBFS-orderings and powers of chordal graphs
• Induced matchings in asteroidal triple-free 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
• Finding a maximum induced matching in weakly chordal graphs
• New results on induced matchings
• Algorithmic Aspects of Vertex Elimination on Graphs
• Bipartite Domination and Simultaneous Matroid Covers
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item