Directed circuits on a torus

P. D. Seymour

doi:10.1007/BF01205078

Directed circuits on a torus

P. D. Seymour

Research output: Contribution to journal › Article › peer-review

8 Scopus citations

Abstract

Given vertices s, t of a planar digraph G, does there exist a directed circuit of G containing both s and t? 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.

Original language	English (US)
Pages (from-to)	261-273
Number of pages	13
Journal	Combinatorica
Volume	11
Issue number	3
DOIs	https://doi.org/10.1007/BF01205078
State	Published - Sep 1991
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Keywords

AMS subject classification (1980): 05C70, 05C10, 05C20, 05C38

Access to Document

10.1007/BF01205078

Cite this

@article{c2ddfcde7dd34d4189809fd535885772,

title = "Directed circuits on a torus",

abstract = "Given vertices s, t of a planar digraph G, does there exist a directed circuit of G containing both s and t? 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 = "AMS subject classification (1980): 05C70, 05C10, 05C20, 05C38",

author = "Seymour, {P. D.}",

year = "1991",

month = sep,

doi = "10.1007/BF01205078",

language = "English (US)",

volume = "11",

pages = "261--273",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "3",

}

TY - JOUR

T1 - Directed circuits on a torus

AU - Seymour, P. D.

PY - 1991/9

Y1 - 1991/9

N2 - Given vertices s, t of a planar digraph G, does there exist a directed circuit of G containing both s and t? 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.

AB - Given vertices s, t of a planar digraph G, does there exist a directed circuit of G containing both s and t? 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.

KW - AMS subject classification (1980): 05C70, 05C10, 05C20, 05C38

UR - http://www.scopus.com/inward/record.url?scp=0347026429&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0347026429&partnerID=8YFLogxK

U2 - 10.1007/BF01205078

DO - 10.1007/BF01205078

M3 - Article

AN - SCOPUS:0347026429

SN - 0209-9683

VL - 11

SP - 261

EP - 273

JO - Combinatorica

JF - Combinatorica

IS - 3

ER -

Directed circuits on a torus

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this