Name
Abstract | ||
|---|---|---|
For a set of vertices of a connected graph , a is a connected subgraph of such that and is minimum. Vertices in are called . In this work, we design an algorithm for the enumeration of all Steiner -trees for a constant number of terminals, which is the usual scenario in many applications. We discuss algorithmic issues involving space requirements to compactly represent the optimal solutions and the time delay to generate them. After generating the first Steiner -tree in polynomial time, our algorithm enumerates the remaining trees with delay (where ). An algorithm to enumerate all Steiner trees was already known (Khachiyan et al., SIAM J Discret Math 19:966–984, ), but this is the first one achieving polynomial delay. A by-product of our algorithm is a representation of all (possibly exponentially many) optimal solutions using polynomially bounded space. We also deal with the following problem: given and a vertex , is in a Steiner -tree for some ? This problem is investigated from the complexity point of view. We prove that it is NP-hard when has arbitrary size. In addition, we prove that deciding whether is in some Steiner -tree is NP-hard as well. We discuss how these problems can be used to define a notion of Steiner convexity in graphs. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s10479-014-1607-5 | Annals OR |
Keywords | Field | DocType |
Complexity of algorithms,Enumerative combinatorics,Steiner convexity,Steiner tree | Discrete mathematics,Mathematical optimization,Combinatorics,Convexity,Polynomial,Vertex (geometry),Steiner tree problem,Enumerative combinatorics,Time complexity,Connectivity,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
223 | 1 | 0254-5330 |
Citations | PageRank | References |
1 | 0.35 | 13 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mitre Dourado | 1 | 90 | 18.43 |
| Rodolfo Alves de Oliveira | 2 | 4 | 1.45 |
| Fábio Protti | 3 | 357 | 46.14 |