Optimizing weakly triangulated graphs
From MaRDI portal
Publication:1822967
DOI10.1007/BF01788689zbMath0679.68082OpenAlexW4230526896WikidataQ56656645 ScholiaQ56656645MaRDI QIDQ1822967
Publication date: 1989
Published in: Graphs and Combinatorics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01788689
optimization problemsmaximum cliquemaximum stable setweakly triangulated graphsminimum clique coveringminimum colouring
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)
Related Items (43)
Alternating cycle-free matchings ⋮ A vertex incremental approach for maintaining chordality ⋮ Algorithms for interval catch digraphs ⋮ Slightly triangulated graphs are perfect ⋮ Alternating orientation and alternating colouration of perfect graphs ⋮ Tolerance intersection graphs of degree bounded subtrees of a tree with constant tolerance 2 ⋮ Unnamed Item ⋮ Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time ⋮ What Is between Chordal and Weakly Chordal Graphs? ⋮ Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems ⋮ Opposition graphs are strict quasi-parity graphs ⋮ Even pairs and the strong perfect graph conjecture ⋮ Finding clubs in graph classes ⋮ Minimum weighted clique cover on claw‐free perfect graphs ⋮ Generating weakly chordal graphs from arbitrary graphs ⋮ Nonvanishing Betti numbers of edge ideals of weakly chordal graphs ⋮ On domination elimination orderings and domination graphs ⋮ Induced matchings in asteroidal triple-free graphs ⋮ A min-max property of chordal bipartite graphs with applications ⋮ Sum-perfect graphs ⋮ A new characterization of HH-free graphs ⋮ On the structure of bull-free perfect graphs ⋮ Preperfect graphs ⋮ Representing edge intersection graphs of paths on degree 4 trees ⋮ On Roussel-Rubio-type lemmas and their consequences ⋮ Approximation of knapsack problems with conflict and forcing graphs ⋮ A Note on k-Colorability of P 5-Free Graphs ⋮ Maximal sub-triangulation in pre-processing phylogenetic data ⋮ The complexity of dissociation set problems in graphs ⋮ The induced matching and chain subgraph cover problems for convex bipartite graphs ⋮ Reconfiguration graph for vertex colourings of weakly chordal graphs ⋮ Linearity defect of edge ideals and Fröberg's theorem ⋮ Finding a maximum induced matching in weakly chordal graphs ⋮ On the \(P_ 4\)-structure of perfect graphs. IV: Partner graphs ⋮ Erratum: Optimizing weakly triangulated graphs. [Graphs and Combinatorics 5, 339-349 (1989)] ⋮ Intersection models of weakly chordal graphs ⋮ A separator-based method for generating weakly chordal graphs ⋮ Lower bounds on approximating some variations of vertex coloring problem over restricted graph classes ⋮ A class of perfectly contractile graphs ⋮ Independent packings in structured graphs ⋮ Quasi-star-cutsets and some consequences ⋮ The maximum clique problem ⋮ Polyominos and perfect graphs
Cites Work
This page was built for publication: Optimizing weakly triangulated graphs
