On some polynomially solvable cases and approximate algorithms in the optimal communication tree construction problem

Considering an arbitrary undirected n -vertex graph with nonnegative edge weights, we seek to construct a spanning tree minimizing the sum over all vertices of the maximal weights of the incident edges. We find some particular cases of polynomial solvability and show that the minimal span whose edge...

Full description

Saved in:
Bibliographic Details
Published in:Journal of applied and industrial mathematics 2013-04, Vol.7 (2), p.142-152
Main Authors: Erzin, A. I., Plotnikov, R. V., Shamardin, Yu. V.
Format: Article
Language:English
Subjects:
Algorithms
Applied mathematics
Approximation
Communications networks
Construction
Construction industry
Data transmission
Energy
Euclidean space
Graph theory
Graphs
Linear programming
Mathematical analysis
Mathematical models
Mathematical problems
Mathematics
Mathematics and Statistics
Optimization
Polynomials
Sensors
Studies
Theorems
Wireless communications
Wireless networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Considering an arbitrary undirected n -vertex graph with nonnegative edge weights, we seek to construct a spanning tree minimizing the sum over all vertices of the maximal weights of the incident edges. We find some particular cases of polynomial solvability and show that the minimal span whose edge weights lie in the closed interval [ a, b ] is a -approximate solution, and the problem of constructing a 1.00048-approximate solution is NP-hard. We propose a heuristic polynomial algorithm and perform its a posteriori analysis.
ISSN:1990-4789
1990-4797
DOI:10.1134/S1990478913020038