Additive sparse spanners for graphs with bounded length of largest induced cycle
From MaRDI portal
Publication:2576868
DOI10.1016/j.tcs.2005.05.017zbMath1080.68085OpenAlexW2172159738MaRDI QIDQ2576868
Chenyu Yan, Feodor F. Dragan, Victor Chepoi
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
Related Items (6)
Additive Spanners for Circle Graphs and Polygonal Graphs ⋮ Spanners for bounded tree-length graphs ⋮ Eccentric counts, connectivity and chordality ⋮ Additive spanners and distance and routing labeling schemes for hyperbolic graphs ⋮ Collective additive tree spanners for circle graphs and polygonal graphs ⋮ An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
Cites Work
- 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
- Optimal tree 3-spanners in directed path 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
This page was built for publication: Additive sparse spanners for graphs with bounded length of largest induced cycle