Pith. sign in

REVIEW

Directed Multicut with linearly ordered terminals

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1407.7498 v1 pith:GXBBK22J submitted 2014-07-28 cs.DS cs.CR

Robert F. Erbacher , Trent Jaeger , Nirupama Talele , Jason Teutsch This is my paper · ORCID
classification cs.DScs.CR
keywords directedsizealgorithmapplicationcasecutsetdistinguishededge
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
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.

Discussion (0). Continue with ORCID to comment.

Pith tools