Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs
type: Item
instance of: scholarly article
title: Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs
zbMATH Open document ID: 0960.05094
DOI: 10.1016/S0166-218X(99)00149-3
author: Feodor F. Dragan
published in: Discrete Applied Mathematics
publication date: 2001-05-10T00:00:00Z
review text: For a graph \(G = (V,E)\) a linear ordering \(\sigma\) of the vertices is called a strong ordering of \(G\) if the following property is fulfilled: if \(ab, ac, bd \in E\), \(a <_{\sigma} d\) and \(b <_{\sigma} c\) then \(cd \in E\). In this paper the author considers strongly orderable graphs, i.e.\ graphs that admit a strong ordering of its vertices. Two new characterizations for this class of graphs are presented using elimination orderings on the vertices (quasi-simple elimination) and the edges (simplicial-edge-without-vertex elimination), respectively. These elimination orderings generalize characterizing elimination orderings for strongly chordal and chordal bipartite graphs. It is shown that a strong ordering of a strongly orderable graph can be found in \(O(|V|+ |E|)|V|\) time, leading to a \(O(|V|+ |E|)|V|\) time algorithm for recognizing strongly orderable graphs. Furthermore, the author proves that the class of strongly chordal graphs is properly contained in the class of weakly triangulated graphs that do not contain a sun as induced subgraph. Finally, greedy algorithms for computing minimum coloring, maximum clique, minimum clique partition, and maximum independent set on strongly orderable graphs are given, that run in linear time, provided a special strong ordering (lexicographic quasi-simple elimination ordering) is given.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1395027
zbMATH Keywords: strongly chordal
zbMATH Keywords: chordal bipartite
zbMATH Keywords: recognition algorithm
zbMATH Keywords: greedy algorithm
zbMATH Keywords: elimination ordering
zbMATH Keywords: optimization algorithm
zbMATH Keywords: maximum clique
zbMATH Keywords: minimum coloring
zbMATH Keywords: strongly orderable graph
MaRDI profile type: Publication
cites work: Characterizations of totally balanced matrices
cites work: Labeling algorithms for domination problems in sun-free chordal graphs
cites work: The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
cites work: Q3347930
cites work: Matching and multidimensional matching in chordal and strongly chordal graphs
cites work: Q4373681
cites work: Characterizations of strongly chordal graphs
cites work: Domination, independent domination, and duality in strongly chordal graphs
cites work: Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
cites work: Q3328583
cites work: Perfect Elimination and Chordal Bipartite Graphs
cites work: Weakly triangulated graphs
cites work: Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph
cites work: Greedoids
cites work: A characterization of perfect graphs
cites work: Doubly Lexical Orderings of Matrices
cites work: Three Partition Refinement Algorithms
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
cites work: Doubly lexical ordering of dense 0--1 matrices
cites work: Steiner trees, connected domination and strongly chordal graphs
full work available at URL: s0166-218x(99)00149-3
OpenAlex ID: W1994963913
description: scientific article; zbMATH DE number 1395027