On Distance-Preserving and Domination Elimination Orderings

DOI10.1137/S0895480195291230MaRDI QIDQ4210215zbMATH OpenFDO

Authors Victor Chepoi

Publication date 21 September 1998

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0895480195291230

zbMATH Keywords

breadth-first searchcharacterizationdistance-preserving orderingdomination elimination orderingdomination graphshouse-free weakly modular graphslexicographic breadth-first searchpseudo-peakless functions

Mathematics Subject Classification ID

Distance in graphs (05C12) Structural characterization of families of graphs (05C75) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On distance-preserving elimination orderings in graphs: complexity and algorithms
• LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
• LexBFS-orderings and powers of chordal graphs

Cited in

(17)

• A witness version of the cops and robber game
• On distance-preserving elimination orderings in graphs: complexity and algorithms
• LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
• Graphs of some CAT(0) complexes
• Ambush cops and robbers
• Medians in median graphs and their cube complexes in linear time
• Perfect elimination orderings for symmetric matrices
• Tandem-win graphs
• Weakly Modular Graphs and Nonpositive Curvature
• Characterizations of k-copwin graphs
• Graphs with \(G^p\)-connected medians
• First-order logic axiomatization of metric graph theory
• The complexity of growing a graph
• Medians in median graphs and their cube complexes in linear time
• Cops and robber with decoys
• On distance preserving and sequentially distance preserving graphs
• Edge critical cops and robber

This page was built for publication: On Distance-Preserving and Domination Elimination Orderings

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