Additive sparse spanners for graphs with bounded length of largest induced cycle

DOI10.1016/j.tcs.2005.05.017zbMath1080.68085MaRDI QIDQ2576868

Feodor F. Dragan, Victor Chepoi, Chenyu Yan

Publication date: 29 December 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.05.017

zbMATH Keywords

distance; efficient algorithms; \(k\)-chordal graphs; additive graph spanners

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

Related Items

Additive Spanners for Circle Graphs and Polygonal Graphs, Spanners for bounded tree-length graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reconstructing the shape of a tree from observed dissimilarity data
• Tree 3-spanners on interval, permutation and regular bipartite graphs
• Graphs whose neighborhoods have no special cycles
• Characterizations of strongly chordal graphs
• On sparse spanners of weighted graphs
• Restrictions of minimum spanner problems
• A note on distance approximating trees in graphs
• Incidence graphs of biacyclic hypergraphs
• Doubly lexical ordering of dense 0--1 matrices
• A Separator Theorem for Chordal Graphs
• Doubly Lexical Orderings of Matrices
• Graph spanners
• Dually Chordal Graphs
• Distance Approximating Trees for Chordal and Dually Chordal Graphs
• Additive Tree Spanners
• Distributed Computing: A Locality-Sensitive Approach
• An Optimal Synchronizer for the Hypercube
• Tree Spanners
• Distance approximating spanning trees
• Additive graph spanners
• Tree spanners in planar graphs