×

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.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
68W99 Algorithms in computer science
Full Text: DOI