Minmax strongly connected subgraphs with node penalties. Issue 2 (25th July 2005) - Punnen, Abraham P.
Abstract : We propose anO ( min { m + n  log  n, m  log ∗ n } ) to find a minmax strongly connected spanning subgraph of a digraph withn nodes andm arcs. A generalization of this problem called the minmax strongly connected subgraph problem with node penalties is also considered. AnO ( m  log  n ) algorithm is proposed to solve this general problem. We also discuss ways to improve the average complexity of this algorithm.