LexBFS-orderings and powers of graphs

DOI10.1007/3-540-62559-3_15MaRDI QIDQ6550543zbMATH OpenFDO

Authors Feodor F. Dragan, Falk Nicolai, Andreas Brandstädt

Publication date 5 June 2024

Full work available at URL https://doi.org/10.1007/3-540-62559-3_15

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
• LexBFS-orderings and powers of chordal graphs
• Lexbfs-orderings and powers of hhd-free graphs^∗
• Almost diameter of a house-hole-free graph in linear time via LexBFS
• Perfect elimination orderings of chordal powers of graphs

Cites work

• A Characterization of Certain Ptolemaic Graphs
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• A characterization of ptolemaic graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Approximating the bandwidth for asteroidal triple-free graphs
• Completely separable graphs
• Convexity in Graphs and Hypergraphs
• Distance-hereditary graphs
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• Dominating cliques in distance-hereditary graphs
• Dually chordal graphs
• 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 3891425 (Why is no real title available?)
• scientific article; zbMATH DE number 468643 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• Location on Tree Networks: P-Centre and n-Dispersion Problems
• On powers and centers of chordal graphs
• On the semi-perfect elimination
• Powers of distance-hereditary graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• Weak bipolarizable graphs

Cited in

(6)

• _i-metric graphs: radius, diameter and all eccentricities
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• Certificates in P and subquadratic-time computation of radius, diameter, and all eccentricities in graphs
• The complexity of diameter on H-free graphs
• Obstructions to faster diameter computation: asteroidal sets
• The complexity of diameter on \(H\)-free graphs

This page was built for publication: LexBFS-orderings and powers of graphs

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