Disjoint paths in tournaments

Research output: Contribution to journalArticle

11 Scopus citations

Abstract

Given k pairs of vertices (si, ti) (1≤i≤k) of a digraph G, how can we test whether there exist k vertex-disjoint directed paths from si to ti for 1≤i≤k? This is NP-complete in general digraphs, even for k=2 [2], but for k=2 there is a polynomial-time algorithm when G is a tournament (or more generally, a semicomplete digraph), due to Bang-Jensen and Thomassen [1]. Here we prove that for all fixed k there is a polynomial-time algorithm to solve the problem when G is semicomplete.

Original languageEnglish (US)
Pages (from-to)582-597
Number of pages16
JournalAdvances in Mathematics
Volume270
DOIs
StatePublished - Jan 2 2015

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Disjoint paths
  • Dynamic programming
  • Graph
  • Routing
  • Tournament

Fingerprint Dive into the research topics of 'Disjoint paths in tournaments'. Together they form a unique fingerprint.

  • Cite this