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

From MaRDI portal
Revision as of 20:39, 29 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs
scientific article

    Statements

    Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs (English)
    0 references
    0 references
    10 May 2001
    0 references
    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.
    0 references
    strongly chordal
    0 references
    chordal bipartite
    0 references
    recognition algorithm
    0 references
    greedy algorithm
    0 references
    elimination ordering
    0 references
    optimization algorithm
    0 references
    maximum clique
    0 references
    minimum coloring
    0 references
    strongly orderable graph
    0 references

    Identifiers