Algorithms for weakly triangulated graphs

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (28)

A vertex incremental approach for maintaining chordality ⋮ Recognizing graph search trees ⋮ Unnamed Item ⋮ Edge erasures and chordal graphs ⋮ Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. I ⋮ Symmetric graph-theoretic roles of two-pairs and chords of cycles ⋮ Generating weakly chordal graphs from arbitrary graphs ⋮ Classes of perfect graphs ⋮ Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs ⋮ Finding large holes ⋮ Maximum weight independent sets in odd-hole-free graphs without dart or without bull ⋮ On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem ⋮ An intersection model for multitolerance graphs: efficient algorithms and hierarchy ⋮ Finding dominating induced matchings in \(P_8\)-free graphs in polynomial time ⋮ Approximation of knapsack problems with conflict and forcing graphs ⋮ NP-completeness results for edge modification problems ⋮ Maximal sub-triangulation in pre-processing phylogenetic data ⋮ The complexity of dissociation set problems in graphs ⋮ Maximum weight induced multicliques and complete multipartite subgraphs in directed path overlap graphs ⋮ Linearity defect of edge ideals and Fröberg's theorem ⋮ Finding a maximum induced matching in weakly chordal graphs ⋮ Maximum weight independent sets in hole- and co-chair-free graphs ⋮ Unnamed Item ⋮ The Recognition Problem of Graph Search Trees ⋮ A separator-based method for generating weakly chordal graphs ⋮ Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds ⋮ Independent packings in structured graphs ⋮ The \(k\)-separator problem: polyhedra, complexity and approximation results

Cites Work

This page was built for publication: Algorithms for weakly triangulated graphs