Algorithms for finding maximum transitive subtournaments

Lasse Kiviluoto, Patric R J Östergård*, Vesa P. Vaskelainen

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

Abstract

The problem of finding a maximum clique is a fundamental problem for undirected graphs, and it is natural to ask whether there are analogous computational problems for directed graphs. Such a problem is that of finding a maximum transitive subtournament in a directed graph. A tournament is an orientation of a complete graph; it is transitive if the occurrence of the arcs xy and yz implies the occurrence of xz. Searching for a maximum transitive subtournament in a directed graph D is equivalent to searching for a maximum induced acyclic subgraph in the complement of D, which in turn is computationally equivalent to searching for a minimum feedback vertex set in the complement of D. This paper discusses two backtrack algorithms and a Russian doll search algorithm for finding a maximum transitive subtournament, and reports experimental results of their performance.

Original languageEnglish
Pages (from-to)802-814
Number of pages13
JournalJOURNAL OF COMBINATORIAL OPTIMIZATION
Volume31
Issue number2
DOIs
Publication statusPublished - 1 Feb 2016
MoE publication typeA1 Journal article-refereed

Keywords

  • Backtrack search
  • Clique
  • Directed acyclic graph
  • Feedback vertex set
  • Russian doll search
  • Transitive tournament

Fingerprint

Dive into the research topics of 'Algorithms for finding maximum transitive subtournaments'. Together they form a unique fingerprint.

Cite this