TY - GEN
T1 - Constructing min-cost single failure immune recovery trees
T2 - 2010 IEEE 4th International Symposium on Advanced Networks and Telecommunication Systems, ANTS 2010
AU - Fang, Xi
AU - Yang, Dejun
AU - Xue, Guoliang
AU - Thulasiraman, Krishnaiyan
PY - 2010/12/1
Y1 - 2010/12/1
N2 - In this paper, we study the problem of constructing min-cost single-link/node failure immune recovery trees for two-edge/vertex connected networks. We prove its NP-hardness, and present a general framework of efficient approximation algorithms for solving this problem. Based on this framework, we present two realizations: 1) for link failure protection, our realization has an approximation ratio of 2 and O(nlog n(m +nlogn)) running time if different links have different costs, or an approximation ratio of 1.5 and a linear running time if all links have the same cost; 2) for node failure protection, our realization has an approximation ratio of 2 and O(n3m) running time if different links have different costs, or an approximation ratio of 5/3 and a linear running time if all links have the same cost.
AB - In this paper, we study the problem of constructing min-cost single-link/node failure immune recovery trees for two-edge/vertex connected networks. We prove its NP-hardness, and present a general framework of efficient approximation algorithms for solving this problem. Based on this framework, we present two realizations: 1) for link failure protection, our realization has an approximation ratio of 2 and O(nlog n(m +nlogn)) running time if different links have different costs, or an approximation ratio of 1.5 and a linear running time if all links have the same cost; 2) for node failure protection, our realization has an approximation ratio of 2 and O(n3m) running time if different links have different costs, or an approximation ratio of 5/3 and a linear running time if all links have the same cost.
UR - http://www.scopus.com/inward/record.url?scp=80052867903&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=80052867903&partnerID=8YFLogxK
U2 - 10.1109/ANTS.2010.5983527
DO - 10.1109/ANTS.2010.5983527
M3 - Conference contribution
AN - SCOPUS:80052867903
SN - 9781424498543
T3 - International Symposium on Advanced Networks and Telecommunication Systems, ANTS
SP - 55
EP - 57
BT - 2010 IEEE 4th International Symposium on Advanced Networks and Telecommunication Systems, ANTS 2010
Y2 - 16 December 2010 through 18 December 2010
ER -