|
 
|
[WWB13] Steiner Problems with Limited Number of Branching Nodes
Conférence Internationale avec comité de lecture : Structural Information and Communication Complexity, July 2013, pp.310-321, Series Lecture notes in computer science, (DOI: 10.1007/978-3-319-03578-9_26)Mots clés: graph algorithm; parameterized complexity; Steiner tree
Résumé:
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 ε < 1.
Equipe:
oc
BibTeX
| @inproceedings { | |||
| WWB13, | |||
| title | = | "{Steiner Problems with Limited Number of Branching Nodes}", | |
| author | = | " D. Watel and M. Weisser and C. Bentz and D. Barth ", | |
| booktitle | = | "{Structural Information and Communication Complexity}", | |
| year | = | 2013, | |
| month | = | "July", | |
| series | = | "Lecture notes in computer science", | |
| pages | = | "310-321", | |
| doi | = | "10.1007/978-3-319-03578-9_26", | |
| } | |||
