Name
Abstract | ||
|---|---|---|
Degree-constrained spanning problems are well known and are mainly used to solve capacity constrained routing problems. The degree-constrained spanning tree problems are NP-hard and computing the minimum cost spanning tree is not approximable. Often, applications (such as some degree-constrained communications) do not need trees as solutions. Recently, a more flexible, connected, graph related structure called hierarchy was proposed to span a set of vertices under constraints. This structure permits a new formulation of some degree-constrained spanning problems. In this paper we show that although the newly formulated problem is still NP-hard, it is approximable with a constant ratio. In the worst case, this ratio is bounded by 3/2. We provide a simple heuristic and prove its approximation ratio is the best possible for any algorithm based on a minimum spanning tree. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-319-09620-9_9 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
Graph theory,Networks,Degree-Constrained Spanning Problem,Spanning Hierarchy,Approximation | Discrete mathematics,Combinatorics,Distributed minimum spanning tree,k-minimum spanning tree,Euclidean minimum spanning tree,Connected dominating set,Spanning tree,Shortest-path tree,Mathematics,Kruskal's algorithm,Minimum spanning tree | Conference |
Volume | ISSN | Citations |
8576 | 0302-9743 | 1 |
PageRank | References | Authors |
0.40 | 19 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Miklós Molnár | 1 | 3 | 1.47 |
| Sylvain Durand | 2 | 6 | 2.63 |
| Massinissa Merabet | 3 | 2 | 0.76 |