Directed circuits on a torus

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)261-273
Number of pages13
JournalCombinatorica
Volume11
Issue number3
DOIs
StatePublished - Sep 1 1991
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Keywords

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

Fingerprint Dive into the research topics of 'Directed circuits on a torus'. Together they form a unique fingerprint.

  • Cite this