Name
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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/s10878-014-9788-z | Journal of Combinatorial Optimization |
Keywords | Field | DocType |
Backtrack search, Clique, Directed acyclic graph, Feedback vertex set, Russian doll search, Transitive tournament | Discrete mathematics,Complete graph,Combinatorics,Transitive reduction,Algorithm,Directed graph,Directed acyclic graph,Transitive closure,Dependency graph,Feedback vertex set,Mathematics,Feedback arc set | Journal |
Volume | Issue | ISSN |
31 | 2 | 1573-2886 |
Citations | PageRank | References |
0 | 0.34 | 21 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lasse Kiviluoto | 1 | 5 | 1.15 |
| Patric R. J. Östergård | 2 | 609 | 70.61 |
| Vesa P. Vaskelainen | 3 | 9 | 1.25 |