Name
Abstract | ||
|---|---|---|
There are n points in the plane and each point is painted by one of m colors where m ≤ n. We want to select m different color points such that (1) the total edge length of resulting minimal spanning tree is as small as possible; or
(2) the total edge length of resulting minimal spanning tree is as large as possible; or (3) the perimeter of the convex hull
of m different color points is as small as possible. We prove NP-completeness for those three problems and give approximations
algorithms for the third problem.
|
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-17458-2_5 | Conference on Combinatorial Optimization and Applications |
Keywords | Field | DocType |
convex hull,approximations algorithm,n point,total edge length,m different color point,m color,minimal spanning tree | Discrete mathematics,Combinatorics,Minimum degree spanning tree,Convex hull,Euclidean minimum spanning tree,Perimeter,Voronoi diagram,Spanning tree,Completeness (statistics),Mathematics,Minimum spanning tree | Conference |
Volume | ISSN | ISBN |
6508 | 16113349 | 3-642-17457-4 |
Citations | PageRank | References |
2 | 0.38 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ovidiu Daescu | 1 | 276 | 45.78 |
| Wenqi Ju | 2 | 19 | 3.24 |
| Jun Luo | 3 | 222 | 26.61 |