Name
Title | ||
|---|---|---|
Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals |
Abstract | ||
|---|---|---|
In this work we present an enumeration algorithm for the generation of all Steiner trees containing a given set W of terminals of an unweighted graph G such that |W|=k, for a fixed positive integer k. The enumeration is performed within O(n) delay, where n=|V(G)| consequence of the algorithm is that the Steiner interval and the strong Steiner interval of a subset W⊆V(G) can be computed in polynomial time, provided that the size of W is bounded by a constant. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.endm.2009.11.053 | Electronic Notes in Discrete Mathematics |
Keywords | DocType | Volume |
Steiner tree,steiner convexity,enumerative combinatorics | Journal | 35 |
ISSN | Citations | PageRank |
1571-0653 | 3 | 0.42 |
References | Authors | |
8 | 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 |