Publikace na Matematicko-fyzikální fakulta |
2009
Abstrakt
Zahajujeme systematickou studii parametrizované složitosti tří základních problémů designu sítí na hranově vážených orientovaných grafech: Orientovaný Steinerův strom, Silně souvislý Steinerův podgraf a Orientovaná Steinerova síť. Zkoumáme jejich parametrizované složitosti vzhledem k parametrům "počet terminálů", "horní mez na velikost propojující sítě" a jejich kombinaci.
Ukážeme několik výsledků parametrizované nedostupnosti a také několik parametrizovaných dostupností, čímž značně rozšíříme předchozí výsledky Feldmana a Ruhla [SIAM J. Comp. 2006].