The MST of symmetric disk graphs is light

DOI10.1016/J.COMGEO.2011.08.002MaRDI QIDQ425622zbMATH OpenOpenAlexFDO

Authors A. Karim Abu-Affash, Rom Aschner, Paz Carmi, Matthew J. Katz

Publication date 8 June 2012

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2011.08.002

zbMATH Keywords

MSTgap theoremsymmetric disk graphwireless communication network

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Network design and communication in computer systems (68M10)

Recommendations

• The MST of symmetric disk graphs is light
• The MST of symmetric disk graphs (in arbitrary metric spaces) is light
• The MST of symmetric disk graphs (in arbitrary metric spaces) is light
• On approximation algorithms of \(k\)-connected \(m\)-dominating sets in disk graphs
• On the Geršgorin disks of distance matrices of graphs
• A new characterization of disk graphs and its application.
• scientific article; zbMATH DE number 4144019
• Approximation and Online Algorithms
• Light graphs in planar graphs of large girth
• Better Approximation Schemes for Disk Graphs

Cites work

• Geometric Spanner Networks
• Introduction to algorithms.
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• On sparse spanners of weighted graphs
• Power consumption in packet radio networks
• The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension

Cited in

(3)

• The MST of symmetric disk graphs is light
• The MST of symmetric disk graphs (in arbitrary metric spaces) is light
• The MST of symmetric disk graphs (in arbitrary metric spaces) is light

This page was built for publication: The MST of symmetric disk graphs is light

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