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.
Similar content being viewed by others
Author information
Authors and Affiliations
Corresponding author
Additional information
Final version received: October 15, 2003
Rights and permissions
About this article
Cite this article
Volgenant, A., Duin, C. On Steiner Versions of (bi)Connectivity in Network Problems. Graphs and Combinatorics 20, 263–273 (2004). https://doi.org/10.1007/s00373-004-0554-3
Received:
Issue Date:
DOI: https://doi.org/10.1007/s00373-004-0554-3