Name
Abstract | ||
|---|---|---|
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. |
Year | Venue | Field |
|---|---|---|
2014 | CoRR | Discrete mathematics,Combinatorics,Vertex (geometry),Parametrization,Network security,Directed graph,Mathematics |
DocType | Volume | Citations |
Journal | abs/1407.7498 | 1 |
PageRank | References | Authors |
0.36 | 12 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Robert F. Erbacher | 1 | 202 | 27.65 |
| T Jaeger | 2 | 2635 | 255.67 |
| Nirupama Talele | 3 | 30 | 3.02 |
| Jason Teutsch | 4 | 120 | 16.84 |