LexBFS-ordering in asteroidal triple-free graphs

DOI10.1007/3-540-46632-0_17MaRDI QIDQ4511223zbMATH OpenFDO

Authors Jou-Ming Chang, Chin-Wen Ho, Ming-Tat Ko

Publication date 12 August 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-46632-0_17

zbMATH Keywords

AT-free graphsLexBFS-orderingLexicographic Breadth-First Searchlinear time recognition algorithmpermutation graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Review text

The authors derive from a result of \textit{D. G. Corneil, S. Olariu} and \textit{L. Stewart} [Linear time algorithms for dominating pairs in asteroidal triple-free graphs, SIAM J. Comput. 28, No.~4, 1284-1297 (1999; Zbl 0926.68094)] that the vertex ordering \(<\) of an AT-free graph \(G\) obtained by applying the Lexicographic Breadth-First Search (LexBFS) twice to \(G\), where the second LexBFS procedure starts in the last vertex of the first LexBFS, has the following metric property: If \(u < v < w\) and \(d(u,w) \leq 2\) then \(d(u,v) = 1\) or \(d(v,w) \leq 2\). The authors modify this ordering to provide a new and simple linear time recognition algorithm for AT-free bipartite graphs (i.e. bipartite permutation graphs). The first linear time recognition algorithm for AT-free bipartite graphs was found by \textit{J. Spinrad, A. Brandstädt} and \textit{L. Stewart} [Bipartite permutation graphs, Discrete Appl. Math. 18, 279-292 (1987; Zbl 0628.05055)]. For the entire collection see [Zbl 0933.00045].

Recommendations

• Characterising AT-free graphs with BFS
• End-vertices of LBFS of (AT-free) bigraphs
• Linear Orderings of Subfamilies of AT‐Free Graphs
• scientific article; zbMATH DE number 1303554

Cited in

(7)

• LexBFS-orderings and powers of chordal graphs
• Induced matchings in asteroidal triple-free graphs
• Characterising AT-free graphs with BFS
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• Vertex ranking of asteroidal triple-free graphs
• End-vertices of LBFS of (AT-free) bigraphs
• Separator orders in interval, cocomparability, and AT-free graphs

This page was built for publication: LexBFS-ordering in asteroidal triple-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4511223)