On spanners and lightweight spanners of geometric graphs

DOI10.1137/080737708zbMATH Open1221.05294OpenAlexW2018527525MaRDI QIDQ3068627FDOQ3068627

Authors: Ljubomir Perković, Ge Xia, Iyad Kanj 

Publication date: 17 January 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/5bf7bfed49c03ed20b11c25f4d27599da57e91df

Recommendations

• On Spanners of Geometric Graphs
• Computing Lightweight Spanners Locally
• On geometric spanners of Euclidean and unit disk graphs
• EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER
• Efficient construction of low weight bounded degree planar spanner

zbMATH Keywords

Delaunay triangulationsbounded degreespannersunit disk graphslightweightlocal distributed algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Distributed algorithms (68W15)

Cited In (22)

• Packing short plane spanning trees in complete geometric graphs
• On certain geometric properties of the Yao-Yao graphs
• On geometric spanners of Euclidean and unit disk graphs
• Packing plane spanning graphs with short edges in complete geometric graphs
• Local approximation schemes for topology control
• Bounded-degree plane geometric spanners in practice
• Efficient construction of low weight bounded degree planar spanner
• Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges
• DISTRIBUTED SPANNERS WITH BOUNDED DEGREE FOR WIRELESS AD HOC NETWORKS
• Spanners for geometric intersection graphs with applications
• Computing Lightweight Spanners Locally
• Spanners of Complete k-Partite Geometric Graphs
• ON SPANNERS OF GEOMETRIC GRAPHS
• On Spanners of Geometric Graphs
• Improved local algorithms for spanner construction
• On plane geometric spanners: a survey and open problems
• On bounded degree plane strong geometric spanners
• Algorithms and Computation
• Light Euclidean Spanners with Steiner Points
• On the stretch factor of Delaunay triangulations of points in convex position
• On a Family of Strong Geometric Spanners That Admit Local Routing Strategies
• Spanners for Geometric Intersection Graphs

This page was built for publication: On spanners and lightweight spanners of geometric graphs

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