Minmax strongly connected subgraphs with node penalties (Q930773)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Minmax strongly connected subgraphs with node penalties |
scientific article; zbMATH DE number 5295962
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Minmax strongly connected subgraphs with node penalties |
scientific article; zbMATH DE number 5295962 |
Statements
Minmax strongly connected subgraphs with node penalties (English)
0 references
1 July 2008
0 references
Summary: We propose an \(O(\min\{m+n\log n,m\log^*n\})\) to find a minmax strongly connected spanning subgraph of a digraph with \(n\) nodes and \(m\) arcs. A generalization of this problem called the minmax strongly connected subgraph problem with node penalties is also considered. An \(O(m\log n)\) algorithm is proposed to solve this general problem. We also discuss ways to improve the average complexity of this algorithm.
0 references
