Improved algorithms for weakly chordal graphs

DOI10.1145/1240233.1240237zbMath1321.05265MaRDI QIDQ2944551

Ryan B. Hayward, R. Sritharan, Jeremy P. Spinrad

Publication date: 2 September 2015

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1240233.1240237

zbMATH Keywords

recognition; graph algorithms; perfect graphs; coloring; weakly chordal

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

05C17: Perfect graphs

Related Items

A separator-based method for generating weakly chordal graphs, Generating weakly chordal graphs from arbitrary graphs, The cluster deletion problem for cographs, Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs, Maximum weight independent sets in odd-hole-free graphs without dart or without bull, Transitive orientations in bull-reducible Berge graphs, Maximum weight independent sets in hole- and co-chair-free graphs, Coloring Artemis graphs, Mock threshold graphs, Approximation of knapsack problems with conflict and forcing graphs, A \(\frac{5}{2}\)-approximation algorithm for coloring rooted subtrees of a degree 3 tree, On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs, Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds, Linear layouts of weakly triangulated graphs, A Characterization of b-Perfect Graphs