2020
Exact algorithms for maximum transitive subgraph problem
Publication
Publication
Presented at the
Cologne-Twente Workshop on Graphs and Combinatorial Optimization (June 2017), Cologne
We study the problem of computing a Maximum Transitive Subgraph (MTS) of a given directed graph. This problem is known to be NP-hard. We give an algorithm that runs in time O(4k2n2) to output an MTS for a graph with treewidth k.
| Additional Metadata | |
|---|---|
| Cologne-Twente Workshop on Graphs and Combinatorial Optimization | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Chakraborty, S., & Jha, N. (2020). Exact algorithms for maximum transitive subgraph problem. In Proceedings of 15th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2017 (pp. 47–51). |
|
