The Minimum Spanning Strong Subdigraph P
✍
Jørgen Bang-Jensen; Anders Yeo
📂
Article
📅
2001
🏛
Elsevier Science
🌐
English
⚖ 148 KB
We consider the problem (minimum spanning strong subdigraph (MSSS)) of finding the minimum number of arcs in a spanning strongly connected subdigraph of a strongly connected digraph. This problem is NP-hard for general digraphs since it generalizes the Hamiltonian cycle problem. We characterize the