  


On the Survivable Network Design Problem with Mixed Connectivity Requirements
E. Sadeghi(sadeghiemail.arizona.edu) Abstract: A graph is said to be $(k,l)$connected if the resulted graph after removing of any $k$ vertices and $(l1)$ edges or removing of any $(k1)$ vertices and $l$ edges is still connected. Beineke and Harary (1967) (see \cite{BeiH67}) claimed to prove that there should be $k+l$ edgedisjoint paths, of which $k$ are vertexdisjoint, 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$ vertexdisjoint 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  