On Steiner Versions of (bi)Connectivity in Network Problems | Graphs and Combinatorics Skip to main content
Log in

On Steiner Versions of (bi)Connectivity in Network Problems

  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Similar content being viewed by others

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to A. Volgenant.

Additional information

Final version received: October 15, 2003

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-004-0554-3

Key words.

Navigation