Algorithmic aspects of Steiner convexity and enumeration of Steiner trees

Mitre Dourado (), Rodolfo Oliveira () and Fábio Protti ()

Annals of Operations Research, 2014, vol. 223, issue 1, 155-171

Abstract: For a set $$W$$ W of vertices of a connected graph $$G=(V(G),E(G))$$ G = ( V ( G ) , E ( G ) ) , a Steiner W-tree is a connected subgraph $$T$$ T of $$G$$ G such that $$W\subseteq V(T)$$ W ⊆ V ( T ) and $$|E(T)|$$ | E ( T ) | is minimum. Vertices in $$W$$ W are called terminals. In this work, we design an algorithm for the enumeration of all Steiner $$W$$ W -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 $$W$$ W -tree in polynomial time, our algorithm enumerates the remaining trees with $$O(n)$$ O ( n ) delay (where $$n=|V(G)|$$ n = | V ( G ) | ). An algorithm to enumerate all Steiner trees was already known (Khachiyan et al., SIAM J Discret Math 19:966–984, 2005 ), 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 $$W$$ W and a vertex $$x\in V(G)\setminus W$$ x ∈ V ( G ) \ W , is $$x$$ x in a Steiner $$W'$$ W ′ -tree for some $$\emptyset \ne W' \subseteq W$$ ∅ ≠ W ′ ⊆ W ? This problem is investigated from the complexity point of view. We prove that it is NP-hard when $$W$$ W has arbitrary size. In addition, we prove that deciding whether $$x$$ x is in some Steiner $$W$$ W -tree is NP-hard as well. We discuss how these problems can be used to define a notion of Steiner convexity in graphs. Copyright Springer Science+Business Media New York 2014

Keywords: Complexity of algorithms; Enumerative combinatorics; Steiner convexity; Steiner tree (search for similar items in EconPapers)
Date: 2014
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-014-1607-5 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:223:y:2014:i:1:p:155-171:10.1007/s10479-014-1607-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-014-1607-5

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().