{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:27:00Z","timestamp":1787340420270,"version":"build-2736575974"},"reference-count":39,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>Given a complete undirected graph, a cost function on edges, and a degree bound B, the degree bounded network design problem is to find a minimum cost simple subgraph with maximum degree B satisfying given connectivity requirements. Even for a simple connectivity requirement such as finding a spanning tree, computing a feasible solution for the degree bounded network design problem is already NP-hard, and thus there is no polynomial factor approximation algorithm for this problem. In this paper, we show that when the cost function satisfies the triangle inequality, there are constant factor approximation algorithms for various degree bounded network design problems. In global edge-connectivity, there is a $(2+\\frac{1}{k})$-approximation algorithm for the minimum bounded degree k-edge-connected subgraph problem. In local edge-connectivity, there is a 4-approximation algorithm for the minimum bounded degree Steiner network problem when $r_{\\max}$ is even, and a 5.5-approximation algorithm when $r_{\\max}$ is odd, where $r_{\\max}$ is the maximum connectivity requirement. In global vertex-connectivity, there is a $(2+\\frac{k-1}{n}+\\frac{1}{k})$-approximation algorithm for the minimum bounded degree k-vertex-connected subgraph problem when $n\\geq2k$, where n is the number of vertices. For spanning tree, there is a $(1+\\frac{1}{B-1})$-approximation algorithm for the minimum bounded degree spanning tree problem. These approximation algorithms return solutions with the smallest possible maximum degree, and in most cases the cost guarantee is obtained by comparing to the optimal cost when there are no degree constraints. This demonstrates that degree constraints can be incorporated into network design problems with metric costs. Our algorithms can be seen as a generalization of Christofides' algorithm for the metric traveling salesman problem. The main technical tool is a simplicity-preserving edge splitting-off operation, which is used to \u201cshort-cut\u201d vertices with high degree while maintaining connectivity requirements and preserving simplicity of the solutions.<\/jats:p>","DOI":"10.1137\/090746495","type":"journal-article","created":{"date-parts":[[2011,7,7]],"date-time":"2011-07-07T18:24:20Z","timestamp":1310063060000},"page":"953-980","source":"Crossref","is-referenced-by-count":10,"title":["Degree Bounded Network Design with Metric Costs"],"prefix":"10.1137","volume":"40","author":[{"given":"Yuk Hei","family":"Chan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wai Shing","family":"Fung","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lap Chi","family":"Lau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chun Kong","family":"Yung","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,7,7]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1103-4"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/S0036142993226983"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480197318878"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1119"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"A. Bern\u00e1th and T. Kir\u00e1ly,\n                      A new approach to splitting-off\n                      , in Integer Programming and Combinatorial Optimization, Springer, Berlin, 2008, pp. 401\u2013415.","DOI":"10.1007\/978-3-540-68891-4_28"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/0403027"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-004-1117-3"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0017-7"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/040621806"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588956"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"A. Czumaj and A. Lingas,\n                      \n                        Approximation schemes for minimum-cost\n                        k\n                        -connectivity problems in geometric graphs\n                      \n                      , in Handbook of Approximation Algorithms and Metaheuristics, Chapman & Hall\/CRC, Boca Raton, FL, 2007.","DOI":"10.1201\/9781420010749.ch51"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0862"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0405003"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90589-8"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"A. Frank,\n                      Edge-connection of graphs, digraphs, and hypergraphs\n                      , in More Sets, Graphs and Numbers, Springer, Berlin, 2006, pp. 93\u2013141.","DOI":"10.1007\/978-3-540-32439-3_6"},{"key":"R16","unstructured":"T. Fukunaga,\n                      Approximation Algorithms to the Network Design Problems\n                      , Doctoral Dissertation, Kyoto University, Kyoto, Japan, 2007."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1093\/ietisy\/e90-d.2.432"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"T. Fukunaga and H. Nagamochi,\n                      Network design with edge connectivity and degree constraints\n                      , in Approximation and Online Algorithms, Lecture Notes in Comput. Sci. 4368, Springer, Berlin, 2007, pp. 188\u2013201.","DOI":"10.1007\/11970125_15"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"M. X. Goemans,\n                      Minimum bounded-degree spanning trees\n                      , in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, pp. 273\u2013282.","DOI":"10.1109\/FOCS.2006.48"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170004"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1002"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199364483"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.03.037"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794264585"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1145\/174652.174654"},{"key":"R26","unstructured":"J. Kleinberg, M. Sandler, and A. Slivkins,\n                      Network failure detection and graph connectivity\n                      , in Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004, pp. 76\u201385."},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1027-4"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"G. Kortsarz and Z. Nutov,\n                      Approximating minimum-cost connectivity problems\n                      , in Handbook of Approximation Algorithms and Metaheuristics, T. F. Gonzalez, ed., Chapman & Hall\/CRC, Boca Raton, FL, 2007.","DOI":"10.1201\/9781420010749.ch58"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(02)00013-8"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-0044-3"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"L. C. Lau, J. Naor, M. R. Salavatipour, and M. Singh,\n                      Survivable network design with degree or order constraints\n                      , in Proceedings of the 39th Annual Symposium on Theory of Computing, 2007, pp. 651\u2013660.","DOI":"10.1145\/1250790.1250886"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"L. C. Lau and M. Singh,\n                      Additive approximation for bounded degree survivable network design\n                      , in Proceedings of the 40th Annual Symposium on Theory of Computing, 2008, pp. 759\u2013768.","DOI":"10.1145\/1374376.1374485"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"L. Lov\u00e1sz,\n                      Combinatorial Problems and Exercises\n                      , North\u2013Holland, Amsterdam, 1993.","DOI":"10.1016\/B978-0-444-81504-0.50006-0"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70504-1"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(82)80009-7"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585735"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1007\/BF02293049"},{"key":"R38","unstructured":"A. Schrijver,\n                      Combinatorial Optimization\u2014Polyhedra and Efficiency\n                      , Springer-Verlag, Berlin, 2003."},{"key":"R39","doi-asserted-by":"crossref","unstructured":"M. Singh and L. C. Lau,\n                      Approximating minimum bounded degree spanning trees to within one of optimal\n                      , in Proceedings of the 39th Annual Symposium on Theory of Computing, 2007, pp. 661\u2013670.","DOI":"10.1145\/1250790.1250887"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090746495","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:34:18Z","timestamp":1787337258000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090746495"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/090746495"],"URL":"https:\/\/doi.org\/10.1137\/090746495","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}