Minmax strongly connected subgraphs with node penalties. Issue 2 (25th July 2005)

• Record Type: Journal Article
• Authors: Punnen, Abraham P.
• Is Part Of: Journal of applied mathematics & decision sciences. Volume 2005:Issue 2(2005)
• Page Start: 107
• Page End: 111
• Publication Date: 2005-07-25
• Subjects: Operations research -- Periodicals; Mathematical models -- Periodicals; Statistics -- Periodicals; Quality control -- Periodicals; Mathematical models; Operations research; Quality control; Statistics; Periodicals; 519.05
• DOI: 10.1155/JAMDS.2005.107
• Languages: English
• ISSNs: 1173-9126

Abstract

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.