Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs

DOI10.1016/S0166-218X(99)00149-3zbMath0960.05094OpenAlexW1994963913MaRDI QIDQ1962062

Feodor F. Dragan

Publication date: 10 May 2001

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

Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00149-3

zbMATH Keywords

greedy algorithmmaximum cliqueoptimization algorithmrecognition algorithmminimum coloringchordal bipartitestrongly chordalelimination orderingstrongly orderable graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Computing a minimum paired-dominating set in strongly orderable graphs ⋮ Edge erasures and chordal graphs ⋮ Finding a sun in building-free graphs ⋮ Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs ⋮ \(L(2,1)\)-labeling of dually chordal graphs and strongly orderable graphs ⋮ The Perfect Matching Reconfiguration Problem ⋮ Perfect circular arc coloring ⋮ Strong Chordality of Graphs with Possible Loops ⋮ Coloring squares of graphs via vertex orderings

Cites Work

• Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph
• Domination, independent domination, and duality in strongly chordal graphs
• Weakly triangulated graphs
• Greedoids
• Characterizations of strongly chordal graphs
• Labeling algorithms for domination problems in sun-free chordal graphs
• Matching and multidimensional matching in chordal and strongly chordal graphs
• Doubly lexical ordering of dense 0--1 matrices
• A characterization of perfect graphs
• Characterizations of totally balanced matrices
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• Steiner trees, connected domination and strongly chordal graphs
• Doubly Lexical Orderings of Matrices
• Three Partition Refinement Algorithms
• Algorithmic Aspects of Vertex Elimination on Graphs
• Perfect Elimination and Chordal Bipartite Graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs