Autor:	Erbacher, Robert F., Jaeger, Trent, Talele, Nirupama, Teutsch, Jason
Rok vydání:	2014
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Cryptography and Security D.4.6 G.2.2
Druh dokumentu:	Working Paper
Popis:	Motivated by an application in network security, we investigate the following "linear" case of Directed Mutlicut. Let $G$ be a directed graph which includes some distinguished vertices $t_1, \ldots, t_k$. What is the size of the smallest edge cut which eliminates all paths from $t_i$ to $t_j$ for all $i < j$? We show that this problem is fixed-parameter tractable when parametrized in the cutset size $p$ via an algorithm running in $O(4^p p n^4)$ time. Comment: 12 pages, 1 figure
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1407.7498 Zobrazit plný text záznamu View this record from Arxiv