On Distance-Preserving and Domination Elimination Orderings

DOI10.1137/S0895480195291230zbMath0915.05097MaRDI QIDQ4210215

Victor Chepoi

Publication date: 21 September 1998

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

zbMATH Keywords

characterizationbreadth-first searchlexicographic breadth-first searchdomination elimination orderingdistance-preserving orderingdomination graphshouse-free weakly modular graphspseudo-peakless functions

Mathematics Subject Classification ID

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

Related Items

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