TY - GEN
T1 - On minimum-and maximum-weight minimum spanning trees with neighborhoods
AU - Dorrigiv, Reza
AU - Fraser, Robert
AU - He, Meng
AU - Kamali, Shahin
AU - Kawamura, Akitoshi
AU - López-Ortiz, Alejandro
AU - Seco, Diego
PY - 2013
Y1 - 2013
N2 - We study optimization problems for the Euclidean minimum spanning tree (MST) on imprecise data. To model imprecision, we accept a set of disjoint disks in the plane as input. From each member of the set, one point must be selected, and the MST is computed over the set of selected points. We consider both minimizing and maximizing the weight of the MST over the input. The minimum weight version of the problem is known as the minimum spanning tree with neighborhoods (MSTN) problem, and the maximum weight version (MAX-MSTN) has not been studied previously to our knowledge. We provide deterministic and parameterized approximation algorithms for the MAX-MSTN problem, and a parameterized algorithm for the MSTN problem. Additionally, we present hardness of approximation proofs for both settings.
AB - We study optimization problems for the Euclidean minimum spanning tree (MST) on imprecise data. To model imprecision, we accept a set of disjoint disks in the plane as input. From each member of the set, one point must be selected, and the MST is computed over the set of selected points. We consider both minimizing and maximizing the weight of the MST over the input. The minimum weight version of the problem is known as the minimum spanning tree with neighborhoods (MSTN) problem, and the maximum weight version (MAX-MSTN) has not been studied previously to our knowledge. We provide deterministic and parameterized approximation algorithms for the MAX-MSTN problem, and a parameterized algorithm for the MSTN problem. Additionally, we present hardness of approximation proofs for both settings.
UR - http://www.scopus.com/inward/record.url?scp=84894170611&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84894170611&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-38016-7_9
DO - 10.1007/978-3-642-38016-7_9
M3 - Conference contribution
AN - SCOPUS:84894170611
SN - 9783642380150
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 93
EP - 106
BT - Approximation and Online Algorithms - 10th International Workshop, WAOA 2012, Revised Selected Papers
T2 - 10th International Workshop on Approximation and Online Algorithms, WAOA 2012
Y2 - 13 September 2012 through 14 September 2012
ER -