LexBFS-orderings and powers of chordal graphs
Two vertices of the \(k\)th power of a graph \(G\) are adjacent if and only if their distance in \(G\) does not exceed \(k\). The lexicographic breadth-first-search (LexBFS) [see \textit{D. J. Rose}, \textit{R. E. Tarjan} and \textit{G. S. Lueker}, SIAM J. Comput. 5, 266-283 (1976; Zbl 0353.65019)] and the maximum cardinality search (MCS) [see \textit{R. E. Tarjan} and \textit{M. Yannakakis}, SIAM J. Comput. 13, 566-579 (1984; Zbl 0545.68062)] give a perfect elimination ordering of a chordal graph in linear time [see \textit{M. C. Golombic}, Algorithmic graph theory and perfect graphs (1980; Zbl 0541.05054)]. In this paper the authors prove that the LexBFS-ordering of a chordal graph is a common perfect elimination ordering of all odd powers of this graph. Also results concerning even powers and MCS are presented.
- Lexbfs-orderings and powers of hhd-free graphs∗
- Perfect elimination orderings of chordal powers of graphs
- LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
- Lexicographic ordering in graph labellings of cycles paths and complete bipartite graphs
- A note on lexicographic breadth first search for chordal graphs
- scientific article; zbMATH DE number 1522927
- scientific article; zbMATH DE number 7651152
- Cycle-free partial orders and chordal comparability graphs
- scientific article; zbMATH DE number 1305500
- scientific article; zbMATH DE number 4152428
- Algorithmic Aspects of Vertex Elimination on Graphs
- Convexity in Graphs and Hypergraphs
- scientific article; zbMATH DE number 3889566 (Why is no real title available?)
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 1414320 (Why is no real title available?)
- On powers and centers of chordal graphs
- On the semi-perfect elimination
- Perfect elimination orderings of chordal powers of graphs
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Maximum induced matchings for chordal graphs in linear time
- On linear and circular structure of (claw, net)-free graphs
- Graph extremities defined by search algorithms
- Perfect elimination orderings of chordal powers of graphs
- LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
- An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time
- Perfect elimination orderings for symmetric matrices
- Partitioning a graph into convex sets
- Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
- Moplex orderings generated by the LexDFs algorithm
- Vertex elimination orderings for hereditary graph classes
- A faster diameter problem algorithm for a chordal graph, with a connection to its center problem
- Distance problems within Helly graphs and \(k\)-Helly graphs
- On the power of graph searching for cocomparability graphs
- Vertex ordering characterizations of graphs of bounded asteroidal number
- End-vertices of graph search algorithms
- Simple vertex ordering characterizations for graph search
- Doubly Lexical Orderings of Matrices
- On Distance-Preserving and Domination Elimination Orderings
- scientific article; zbMATH DE number 1305500 (Why is no real title available?)
- Lexbfs-orderings and powers of hhd-free graphs∗
- Practical and efficient circle graph recognition
- Practical and efficient split decomposition via graph-labelled trees
- Biclique-colouring verification complexity and biclique-colouring power graphs
- Fast approximation of eccentricities and distances in hyperbolic graphs
- The LexCycle on \(\overline{P_2\cup P_3} \)-free cocomparability graphs
- Induced embeddings into Hamming graphs
- End-vertices of LBFS of (AT-free) bigraphs
- scientific article; zbMATH DE number 7651152 (Why is no real title available?)
- Graph-Theoretic Concepts in Computer Science
- Colouring clique-hypergraphs of circulant graphs
- Colouring clique-hypergraphs of circulant graphs
- A general label search to investigate classical graph search algorithms
- LexBFS-orderings and powers of graphs
- Recognizing LBFS trees of bipartite graphs
- A note on lexicographic breadth first search for chordal graphs
- The partial search order problem
- Maximum induced matching problem on hhd-free graphs
- Collective tree spanners in graphs with bounded parameters
- A tie-break model for graph search
- On end-vertices of lexicographic breadth first searches
This page was built for publication: LexBFS-orderings and powers of chordal graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1363684)
