On the complexity of the planar directed edge-disjoint paths problem

被引：0
作者：
Dirk Müller
机构：
[1] University of Bonn,Research Institute for Discrete Mathematics
来源：
Mathematical Programming | 2006年 / 105卷
关键词：
Edge-disjoint paths; Planar graphs; Integral two-commodity-flows; NP-completeness; Complexity; 05C38; 68Q17; 68R10; 90C35;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
页码：275 / 288
页数：13
相关论文
共 7 条
[1]  
Even undefined(1976)undefined SIAM J. Comput. 5 691-undefined
[2]  
Karp undefined(1975)undefined Networks 5 45-undefined
[3]  
Korach undefined(1993)undefined Discrete Appl. Math. 47 77-undefined
[4]  
Lichtenstein undefined(1982)undefined SIAM J. Comput. 11 329-undefined
[5]  
Middendorf undefined(1)undefined Combinatorica 13 97-undefined
[6]  
Schrijver undefined(1994)undefined SIAM J. Comput. 23 780-undefined
[7]  
Sebő undefined(1993)undefined J. Comb. Theory Ser. B 59 163-undefined
1