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

DOI10.1016/J.TCS.2005.05.017MaRDI QIDQ2576868zbMATH OpenOpenAlexFDO

Authors Victor Chepoi, Feodor F. Dragan, 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

\(k\)-chordal graphsadditive graph spannersdistanceefficient algorithms

Mathematics Subject Classification ID

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

Recommendations

• Structural Information and Communication Complexity
• Additive graph spanners
• Approximating the Longest Cycle Problem in Sparse Graphs
• Additive Spanners for Circle Graphs and Polygonal Graphs
• scientific article; zbMATH DE number 2011848
• The Sparsest Additive Spanner via Multiple Weighted BFS Trees
• The sparsest additive spanner via multiple weighted BFS trees
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• A Lower Bound on Cycle-Finding in Sparse Digraphs
• A Lower Bound on Cycle-Finding in Sparse Digraphs

Cites work

• A note on distance approximating trees in graphs
• A Separator Theorem for Chordal Graphs
• Additive graph spanners
• Additive Tree Spanners
• An Optimal Synchronizer for the Hypercube
• Characterizations of strongly chordal graphs
• Distance approximating spanning trees
• Distance Approximating Trees for Chordal and Dually Chordal Graphs
• Distributed Computing: A Locality-Sensitive Approach
• Doubly lexical ordering of dense 0--1 matrices
• Doubly Lexical Orderings of Matrices
• Dually Chordal Graphs
• Graph spanners
• Graphs whose neighborhoods have no special cycles
• scientific article; zbMATH DE number 434498 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 1107724 (Why is no real title available?)
• scientific article; zbMATH DE number 1979496 (Why is no real title available?)
• scientific article; zbMATH DE number 2044927 (Why is no real title available?)
• Incidence graphs of biacyclic hypergraphs
• On sparse spanners of weighted graphs
• Optimal tree 3-spanners in directed path graphs
• Reconstructing the shape of a tree from observed dissimilarity data
• Restrictions of minimum spanner problems
• Tree 3-spanners on interval, permutation and regular bipartite graphs
• Tree Spanners
• Tree spanners in planar graphs

Cited in

(9)

• Eccentric counts, connectivity and chordality
• Spanners for bounded tree-length graphs
• Additive spanners and distance and routing labeling schemes for hyperbolic graphs
• scientific article; zbMATH DE number 2011848 (Why is no real title available?)
• 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
• Additive graph spanners
• Additive Spanners for Circle Graphs and Polygonal Graphs
• Structural Information and Communication Complexity

This page was built for publication: Additive sparse spanners for graphs with bounded length of largest induced cycle

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