Bounded-angle spanning tree: modeling networks with angular constraints

DOI10.1007/s00453-015-0076-9zbMath1359.68229OpenAlexW1833772674MaRDI QIDQ513267

Matthew J. Katz, Rom Aschner

Publication date: 3 March 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-015-0076-9

zbMATH Keywords

minimum spanning treeapproximation algorithmsNP-hardnesswireless networkspower assignmentdirectional antennashop spanner

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

A 4-approximation of the \(\frac{2\pi }{3} \)-MST ⋮ Improved formulations and branch-and-cut algorithms for the angular constrained minimum spanning tree problem ⋮ Improved algorithms in directional wireless sensor networks ⋮ On solving bi-objective constrained minimum spanning tree problems ⋮ Game of operation of a telecommunication network of agents with directional antennas ⋮ A unifying model for locally constrained spanning tree problems ⋮ Bounded-angle minimum spanning trees ⋮ Unnamed Item ⋮ Minimum Scan Cover with Angular Transition Costs ⋮ Modeling and solving the angular constrained minimum spanning tree problem ⋮ A 4-approximation of the \(\frac{ 2 \pi}{ 3} \)-MST

Cites Work

• Symmetric connectivity with directional antennas
• Drawing Hamiltonian cycles with no large angles
• Connectivity guarantees for wireless networks with directional antennas
• Connectivity with directional antennas in the symmetric communication model
• Maximizing maximal angles for plane straight-line graphs
• Not being (super)thin or solid is hard: A study of grid Hamiltonicity
• Degree-bounded minimum spanning trees
• Power consumption in packet radio networks
• Euclidean bounded-degree spanning tree ratios
• Ice-creams and wedge graphs
• Angle-restricted tours in the plane.
• Paths with No Small Angles
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• On two geometric problems related to the travelling salesman problem
• Min-Power Strong Connectivity
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Hamilton Paths in Grid Graphs
• Low-Degree Spanning Trees of Small Weight
• Bounded-Angle Spanning Tree: Modeling Networks with Angular Constraints
• Switching to Directional Antennas with Constant Increase in Radius and Hop Distance
• Maintaining Connectivity in Sensor Networks Using Directional Antennae
• Geometry helps in bottleneck matching and related problems