Fast Exact Algorithms for Survivable Network Design with Uniform Requirements
Fast Exact Algorithms for Survivable Network Design with Uniform Requirements
复制标题
具有统一要求的可生存网络设计的快速精确算法
作者：
A. Agrawal;P. Misra;Fahad Panolan;Saket Saurabh
We design exact algorithms for the following two problems in survivable network design: (i) designing a minimum cost network with a desired value of edge connectivity, which is called Minimum Weightλdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$lambda $$end{document}-connected Spanning Subgraph and (ii) augmenting a given network to a desired value of edge connectivity at a minimum cost which is called Minimum Weightλdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$lambda $$end{document}-connectivity Augmentation. It is easy to see that a minimum solution to these problems contains at most 2λ(n-1)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$2 lambda (n-1)$$end{document} edges. Using this fact one can design a brute-force algorithm which runs in time 2O(λnlogn)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$2^{{mathcal {O}}(lambda n log n)}$$end{document}, however no better algorithms were known previously. In this paper, we give the first single exponential time algorithm for these problems, i.e. running in time 2O(λn)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$2^{{mathcal {O}}(lambda n)}$$end{document}, for both undirected and directed networks. Our results are obtained via well known characterizations of λdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$lambda $$end{document}-connected graphs, their connections to linear matroids and the recently developed technique of dynamic programming with representative sets.
We design exact algorithms for the following two problems in survivable network design: (i) designing a minimum cost network with a desired value of edge connectivity, which is called Minimum Weightλdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$lambda $$end{document}-connected Spanning Subgraph and (ii) augmenting a given network to a desired value of edge connectivity at a minimum cost which is called Minimum Weightλdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$lambda $$end{document}-connectivity Augmentation. It is easy to see that a minimum solution to these problems contains at most 2λ(n-1)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$2 lambda (n-1)$$end{document} edges. Using this fact one can design a brute-force algorithm which runs in time 2O(λnlogn)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$2^{{mathcal {O}}(lambda n log n)}$$end{document}, however no better algorithms were known previously. In this paper, we give the first single exponential time algorithm for these problems, i.e. running in time 2O(λn)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$2^{{mathcal {O}}(lambda n)}$$end{document}, for both undirected and directed networks. Our results are obtained via well known characterizations of λdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$lambda $$end{document}-connected graphs, their connections to linear matroids and the recently developed technique of dynamic programming with representative sets.