Improved algorithms for weakly chordal graphs

DOI10.1145/1240233.1240237zbMath1321.05265OpenAlexW2099914933MaRDI 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

recognitiongraph algorithmsperfect graphscoloringweakly chordal

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17)

Related Items (15)

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

This page was built for publication: Improved algorithms for weakly chordal graphs