On the complexity of the planar directed edge-disjoint paths problem
成果类型：
Article; Proceedings Paper
署名作者：
Müller, D
署名单位：
University of Bonn
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-005-0653-9
发表日期：
2006
页码：
275-288
关键词：
摘要：
The edge-disjoint paths problem and many special cases of it are known to be NP-complete. We present a new NP-completeness result for a special case of the problem, namely the directed edge-disjoint paths problem restricted to planar supply graphs and demand graphs consisting of two sets of parallel edges.