On Steiner versions of (bi)connectivity in network problems
| Authors | |
|---|---|
| Publication date | 2004 |
| Journal | Graphs and Combinatorics |
| Volume | Issue number | 20 | 2 |
| Pages (from-to) | 263-273 |
| Number of pages | 11 |
| Organisations |
|
| Abstract | The notions of connectivity and biconnectivity can be generalized in the Steiner sense, i.e., they are restricted to a given subset of the vertices of a graph. We illustrate this generalization on two problems. The first problem is the bottleneck biconnected subgraph problem, the second one is the so-called bipartition problem. The adapted algorithms to solve the Steiner versions of these problems exploit depth-first search to attain respectively a running time of O(|E|+|V|log|V|) and O(|E|+|V|) with E denoting the set of edges and V the set of vertices of the given graph. |
| Document type | Article |
| Published at |
https://doi.org/10.1007/s00373-004-0554-3
(Final published version)
|
| Permalink to this page | |