Algorithms for weakly triangulated graphs

DOI10.1016/0166-218X(93)E0161-QzbMath0827.68084MaRDI QIDQ1891926

R. Sritharan, Jeremy P. Spinrad

Publication date: 6 June 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

optimization problemsweakly triangulated graphs

Mathematics Subject Classification ID

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

Related Items (29)

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 ⋮ Graph Search Trees and Their Leaves ⋮ 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

• Unnamed Item
• Unnamed Item
• Weakly triangulated graphs
• Covering orthogonal polygons with star polygons: The perfect graph approach
• Finding large holes
• Erratum: Optimizing weakly triangulated graphs. [Graphs and Combinatorics 5, 339-349 (1989)]
• An efficient algorithm for finding a two-pair, and its applications
• Perfect Graphs and Orthogonally Convex Covers

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