Optimization Online


On the Survivable Network Design Problem with Mixed Connectivity Requirements

E. Sadeghi(sadeghi***at***email.arizona.edu)
Neng Fan(nfan***at***email.arizona.edu)

Abstract: A graph is said to be $(k,l)$-connected if the resulted graph after removing of any $k$ vertices and $(l-1)$ edges or removing of any $(k-1)$ vertices and $l$ edges is still connected. Beineke and Harary (1967) (see \cite{BeiH67}) claimed to prove that there should be $k+l$ edge-disjoint paths, of which $k$ are vertex-disjoint, between any pair of vertices if the graph has $(k,l)$-connectivity. However, Mader (1979) (see \cite{Mader}) pointed out a gap in this proof. In this paper, we first modify the conclusion (by changing to $k+1$ vertex-disjoint paths instead of $k$), and then formally prove it. As an application, we propose to design a $(k,l)$-connected network with minimum cost, by presenting two integer programming (IP) formulations and a cutting plane algorithm. Numerical experiments are performed on randomly generated graphs to compare these approaches.

Keywords: Network design, Connected spanning subgraph, Mixed connectivity, Vertex connectivity, Edge connectivity, Disjoint paths

Category 1: Combinatorial Optimization

Citation: University of Arizona, 09/2015

Download: [PDF]

Entry Submitted: 10/07/2015
Entry Accepted: 10/08/2015
Entry Last Modified: 10/07/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society