A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph (Q1186788)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph |
scientific article |
Statements
A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph (English)
0 references
28 June 1992
0 references
The authors present a linear-time algorithm for finding a sparse \(k\)- connected spanning subgraph for a given \(k\)-connected undirected graph. This is used to improve the time complexities of other graph connectivity problems.
0 references
\(k\)-connected spanning subgraph
0 references
linear-time algorithm
0 references
time complexities
0 references
graph connectivity problems
0 references
