Parameterized complexity of arc-weighted directed Steiner problems. (English) Zbl 1230.05268
This paper deals with parameterized versions of a number of graph-theoretic problems on directed graphs with weights on their edges. In particular, the problems that are considered are the Steiner tree problem, the Steiner subgraph problem as well as the directed Steiner network problem. The authors show that on certain restrictions of the weights of the edges, these problems are W[1]-hard.
Reviewer: Nikolaos Fountoulakis (Edgbaston)
MSC:
05C85 | Graph algorithms (graph-theoretic aspects) |
68R10 | Graph theory (including graph drawing) in computer science |
68W99 | Algorithms in computer science |