Generating sparse spanners for weighted graphs

DOI10.1007/3-540-52846-6_75zbMath1502.68198OpenAlexW1489900072MaRDI QIDQ5056089

David P. Dobkin, Ingo Althöfer, Deborah Joseph, Gautam K. Das

Publication date: 9 December 2022

Published in: SWAT 90 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-52846-6_75

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (9)

Generating sparse spanners for weighted graphs ⋮ Generating sparse 2—spanners ⋮ Covering metric spaces by few trees ⋮ On additive spanners in weighted graphs with local error ⋮ Approximating \(k\)-spanner problems for \(k>2\) ⋮ Covering Metric Spaces by Few Trees ⋮ On graph problems in a semi-streaming model ⋮ Approximating Euclidean distances by small degree graphs ⋮ Graph theoretical issues in computer networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reconstructing the shape of a tree from observed dissimilarity data
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
• Shortest paths in Euclidean graphs
• On optimal realizations of finite metric spaces by graphs
• Complexity of network synchronization
• Graph spanners
• An Optimal Synchronizer for the Hypercube
• Generating sparse spanners for weighted graphs
• A note on the tree realizability of a distance matrix
• Regular d-valent graphs of girth 6 and 2(d2−d+1) vertices

This page was built for publication: Generating sparse spanners for weighted graphs