Parameterized Complexity of Directed Steiner Network with Respect to Shared Vertices and Arcs
| Autor: | Mehdy Roayaei, Mohammadreza Razzazi |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Astrophysics::Instrumentation and Methods for Astrophysics
Minimum weight Parameterized complexity Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) 0102 computer and information sciences 02 engineering and technology Directed graph 01 natural sciences Vertex (geometry) Combinatorics 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Computer Science (miscellaneous) Computer Science::General Literature 020201 artificial intelligence & image processing Output-sensitive algorithm Mathematics |
| Zdroj: | International Journal of Foundations of Computer Science. 29:1215-1230 |
| ISSN: | 1793-6373 0129-0541 |
| Popis: | We consider the directed Steiner network problem, where given a weighted directed graph [Formula: see text] and [Formula: see text] pairs of vertices [Formula: see text], one has to find the minimum weight subgraph [Formula: see text] of [Formula: see text] that contains path from [Formula: see text] to [Formula: see text] for all [Formula: see text]. We search for the main cause of the complexity of the problem and introduce the notions of junction vertex and shared segment in an optimal solution. We study the parameterized complexity of the problem with respect to these parameters and achieve several parameterized hardness results. Also, we present two output-sensitive algorithms for the problem, which are much simpler and easier to implement than the previously best known one; and in addition, when the paths corresponding to the input pairs have few shared vertices or arcs in the optimal solution, these algorithms outperform the previous one. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|