Generating sparse spanners for weighted graphs

DOI10.1007/3-540-52846-6_75MaRDI QIDQ5056089zbMATH OpenOpenAlexFDO

Authors Ingo Althöfer, David P. Dobkin, 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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Signed and weighted graphs (05C22)

Recommendations

• On sparse spanners of weighted graphs
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• scientific article; zbMATH DE number 1617269
• Light spanners
• Light spanners

Cites work

• scientific article; zbMATH DE number 4155926 (Why is no real title available?)
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 140458 (Why is no real title available?)
• scientific article; zbMATH DE number 192896 (Why is no real title available?)
• scientific article; zbMATH DE number 4119974 (Why is no real title available?)
• A note on the tree realizability of a distance matrix
• An Optimal Synchronizer for the Hypercube
• Complexity of network synchronization
• Generating sparse spanners for weighted graphs
• Graph spanners
• On optimal realizations of finite metric spaces by graphs
• Reconstructing the shape of a tree from observed dissimilarity data
• Regular d-valent graphs of girth 6 and 2(d2−d+1) vertices
• Shortest paths in Euclidean graphs
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces

Cited in

(14)

• On graph problems in a semi-streaming model
• Generating sparse 2—spanners
• Approximating Euclidean distances by small degree graphs
• Generating sparse spanners for weighted graphs
• Covering Metric Spaces by Few Trees
• Spanners in randomly weighted graphs: Euclidean case
• On sparse spanners of weighted graphs
• Graph theoretical issues in computer networks
• Approximating \(k\)-spanner problems for \(k>2\)
• scientific article; zbMATH DE number 1617269 (Why is no real title available?)
• Covering metric spaces by few trees
• A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
• On dynamic shortest paths problems
• On additive spanners in weighted graphs with local error

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

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