Steiner Problems with Limited Number of Branching Nodes

Abstract : Given an undirected weighted graph G with n nodes, the k-Undirected Steiner Tree problem is to find a minimum cost tree spanning a specified set of k nodes. If this problem and its directed version have several applications in multicast routing in packet switching networks, the modeling is not adapted anymore in networks based upon the circuit switching principle in which not all nodes are able to duplicate packets. In such networks, the number of branching nodes (with outdegree > 1) in the multicast tree must be limited. We introduce the (k; p)-Steiner Tree with Limited Number of Branching nodes problems where the goal is to find an optimal Steiner tree with at most p branching nodes. We study, when p is fixed, its complexity depending on two criteria: the graph topology and the parameter k. In particular, we propose a polynomial algorithm when the input graph is acyclic and an other algorithm when k is fixed in an input graph of bounded treewidth. Moreover, in directed graphs where p <= k - 2, or in planar graphs, we provide an n -inapproximability proof, for any epsilon < 1.
Document type :
Conference papers
Complete list of metadatas

https://hal-supelec.archives-ouvertes.fr/hal-00877222
Contributor : Elodie Dubrac <>
Submitted on : Monday, October 28, 2013 - 9:18:49 AM
Last modification on : Saturday, February 9, 2019 - 1:26:07 AM

Identifiers

  • HAL Id : hal-00877222, version 1

Citation

Dimitri Watel, Marc-Antoine Weisser, Cédric Bentz, Dominique Barth. Steiner Problems with Limited Number of Branching Nodes. SIROCCO 2013, Jul 2013, Ischia, Italy. ⟨hal-00877222⟩

Share

Metrics

Record views

233