Directed circuits on a torus |
| |
Authors: | P. D. Seymour |
| |
Affiliation: | (1) Bellcore, 445 South St, 07960 Morristown, New Jersey, U.S.A. |
| |
Abstract: | Given verticess, t of a planar digraphG, does there exist a directed circuit ofG containing boths andt? We give a polynomial algorithm for this and for a number of related problems, including one about disjoint directed circuits of prescribed homotopy in a digraph drawn on a torus. |
| |
Keywords: | 05 C 70 05 C 10 05 C 20 05 C 38 |
本文献已被 SpringerLink 等数据库收录! |
|