Pith. sign in

REVIEW

Induced Disjoint Paths in Circular-Arc Graphs in Linear Time

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 1403.0789 v1 pith:5DCDAS7Q submitted 2014-03-04 cs.DS

Petr A. Golovach , Daniël Paulusma , Erik Jan van Leeuwen This is my paper · ORCID
classification cs.DS
keywords pathsdisjointinducedgraphsverticesalgorithmcircular-arcdistinct
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

The Induced Disjoint Paths problem is to test whether a graph G with k distinct pairs of vertices (s_i,t_i) contains paths P_1,...,P_k such that P_i connects s_i and t_i for i=1,...,k, and P_i and P_j have neither common vertices nor adjacent vertices (except perhaps their ends) for 1<=i < j<=k. We present a linear-time algorithm for Induced Disjoint Paths on circular-arc graphs. For interval graphs, we exhibit a linear-time algorithm for the generalization of Induced Disjoint Paths where the pairs (s_i,t_i) are not necessarily distinct.

Discussion (0). Continue with ORCID to comment.

Pith tools