On the complexity of the planar edge-disjoint paths problem with terminals on the outer boundary |
| |
Authors: | Werner Schwärzler |
| |
Institution: | (1) Lufthansa Systems, FRA AS/N, Am Prime Parc 1, D-65479 Raunheim, Germany |
| |
Abstract: | It is shown that both the undirected and the directed edge-disjoint paths problem are NP-complete, if the supply graph is
planar and all edges of the demand graph are incident with vertices lying on the outer boundary of the supply graph. In the
directed case, the problem remains NP-complete, if in addition the supply graph is acyclic. The undirected case solves open
problem no. 56 of A. Schrijver’s book Combinatorial Optimization. |
| |
Keywords: | Mathematics Subject Classification (2000)" target="_blank">Mathematics Subject Classification (2000) 05C38 05C40 |
本文献已被 SpringerLink 等数据库收录! |
|