LexBFS-orderings and powers of chordal graphs
From MaRDI portal
Publication:1363684
DOI10.1016/S0012-365X(96)00070-2zbMath0880.05074MaRDI QIDQ1363684
Falk Nicolai, Feodor F. Dragan, Andreas Brandstädt
Publication date: 19 January 1998
Published in: Discrete Mathematics (Search for Journal in Brave)
Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (29)
Collective tree spanners in graphs with bounded parameters ⋮ The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs ⋮ Graph extremities defined by search algorithms ⋮ A faster diameter problem algorithm for a chordal graph, with a connection to its center problem ⋮ Perfect elimination orderings for symmetric matrices ⋮ Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number ⋮ End-Vertices of Graph Search Algorithms ⋮ A general label search to investigate classical graph search algorithms ⋮ A tie-break model for graph search ⋮ Distance problems within Helly graphs and \(k\)-Helly graphs ⋮ On linear and circular structure of (claw, net)-free graphs ⋮ LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem ⋮ Practical and efficient circle graph recognition ⋮ Practical and efficient split decomposition via graph-labelled trees ⋮ Biclique-colouring verification complexity and biclique-colouring power graphs ⋮ End-vertices of LBFS of (AT-free) bigraphs ⋮ On end-vertices of lexicographic breadth first searches ⋮ An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time ⋮ Partitioning a graph into convex sets ⋮ On the Power of Graph Searching for Cocomparability Graphs ⋮ Vertex elimination orderings for hereditary graph classes ⋮ Colouring clique-hypergraphs of circulant graphs ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ Maximum induced matchings for chordal graphs in linear time ⋮ Colouring clique-hypergraphs of circulant graphs ⋮ Maximum induced matching problem on hhd-free graphs ⋮ Induced Embeddings into Hamming Graphs. ⋮ Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds ⋮ Simple vertex ordering characterizations for graph search
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On powers and centers of chordal graphs
- Perfect elimination orderings of chordal powers of graphs
- On the semi-perfect elimination
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Convexity in Graphs and Hypergraphs
- Algorithmic Aspects of Vertex Elimination on Graphs
This page was built for publication: LexBFS-orderings and powers of chordal graphs
