{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T08:36:10Z","timestamp":1725525370796},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642002014"},{"type":"electronic","value":"9783642002021"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-00202-1_19","type":"book-chapter","created":{"date-parts":[[2009,2,10]],"date-time":"2009-02-10T07:34:01Z","timestamp":1234251241000},"page":"214-225","source":"Crossref","is-referenced-by-count":1,"title":["Network Design with Weighted Degree Constraints"],"prefix":"10.1007","author":[{"given":"Takuro","family":"Fukunaga","sequence":"first","affiliation":[]},{"given":"Hiroshi","family":"Nagamochi","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Bansal, N., Khandekar, R., Nagarajan, V.: Additive guarantees for degree bounded directed network design. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 769\u2013778 (2008)","key":"19_CR1","DOI":"10.1145\/1374376.1374486"},{"key":"19_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/11538462_3","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"K. Chaudhuri","year":"2005","unstructured":"Chaudhuri, K., Rao, S., Riesenfeld, S., Talwar, K.: What would Edmonds do? augmenting paths and witnesses for degree-bounded MSTs. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol.\u00a03624, pp. 26\u201339. Springer, Heidelberg (2005)"},{"key":"19_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/11786986_18","volume-title":"Automata, Languages and Programming","author":"K. Chaudhuri","year":"2006","unstructured":"Chaudhuri, K., Rao, S., Riesenfeld, S., Talwar, K.: A push-relabel algorithm for approximating degree bounded MSTs. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 191\u2013201. Springer, Heidelberg (2006)"},{"issue":"3","key":"19_CR4","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1006\/jagm.1994.1042","volume":"17","author":"M. F\u00fcrer","year":"1994","unstructured":"F\u00fcrer, M., Raghavachari, B.: Approximating the minimum-degree Steiner tree to within one of optimal. Journal of Algorithms\u00a017(3), 409\u2013423 (1994)","journal-title":"Journal of Algorithms"},{"key":"19_CR5","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/j.ipl.2007.06.011","volume":"104","author":"M. Ghodsi","year":"2007","unstructured":"Ghodsi, M., Mahini, H., Mirjalali, K., Gharan, S.O., Sayedi, A.S., Zadimoghaddam, R.M.: Spanning trees with minimum weighted degrees. Information Processing Letters\u00a0104, 113\u2013116 (2007)","journal-title":"Information Processing Letters"},{"doi-asserted-by":"crossref","unstructured":"Goemans, M.X.: Minimum bounded-degree spanning trees. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 273\u2013282 (2006)","key":"19_CR6","DOI":"10.1109\/FOCS.2006.48"},{"key":"19_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Heidelberg (1988)"},{"key":"19_CR8","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s004930170004","volume":"21","author":"K. Jain","year":"2001","unstructured":"Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica\u00a021, 39\u201360 (2001)","journal-title":"Combinatorica"},{"key":"19_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/978-3-540-68891-4_18","volume-title":"Integer Programming and Combinatorial Optimization","author":"T. Kiraly","year":"2008","unstructured":"Kiraly, T., Lau, L.C., Singh, M.: Degree bounded matroids and submodular flows. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008. LNCS, vol.\u00a05035, pp. 259\u2013272. Springer, Heidelberg (2008)"},{"issue":"6","key":"19_CR10","doi-asserted-by":"publisher","first-page":"1783","DOI":"10.1137\/S009753970036917X","volume":"31","author":"J. K\u00f6nemann","year":"2002","unstructured":"K\u00f6nemann, J., Ravi, R.: A matter of degree: Improved approximation algorithms for degree-bounded minimum spanning trees. SIAM Journal on Computing\u00a031(6), 1783\u20131793 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"19_CR11","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1137\/S0097539702418048","volume":"34","author":"J. K\u00f6nemann","year":"2005","unstructured":"K\u00f6nemann, J., Ravi, R.: Primal-dual meets local search: approximating MST\u2019s with nonuniform degree bounds. SIAM Journal on Computing\u00a034, 763\u2013773 (2005)","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"Lau, L.C., Naor, J.S., Singh, M., Salavatipour, M.R.: Survivable network design with degree or order constraints. In: Proceedings of the 39th ACM Symposium on Theory of Computing (STOC), pp. 651\u2013660 (2007)","key":"19_CR12","DOI":"10.1145\/1250790.1250886"},{"doi-asserted-by":"crossref","unstructured":"Lau, L.C., Singh, M.: Additive approximation for bounded degree survivable network design. In: Proceedings of the 40th ACM Symposium on Theory of Computing (STOC), pp. 759\u2013768 (2008)","key":"19_CR13","DOI":"10.1145\/1374376.1374485"},{"key":"19_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-3-540-85363-3_18","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"Z. Nutov","year":"2008","unstructured":"Nutov, Z.: Approximating directed weighted-degree constrained networks. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 219\u2013232. Springer, Heidelberg (2008)"},{"unstructured":"Ravi, R.: Steiner Trees and Beyond: Approximation Algorithms for Network Design. PhD thesis, Department of Computer Science, Brown University (1993)","key":"19_CR15"},{"doi-asserted-by":"crossref","unstructured":"Ravi, R., Marathe, M.V., Ravi, S.S., Rosenkrantz, D.J., Hunt III, H.B.: Many birds with one stone: Multi-objective approximation algorithms. In: Proceedings of the 25th ACM Symposium on Theory of Computing, pp. 438\u2013447 (1993)","key":"19_CR16","DOI":"10.1145\/167088.167209"},{"key":"19_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/11786986_16","volume-title":"Automata, Languages and Programming","author":"R. Ravi","year":"2006","unstructured":"Ravi, R., Singh, M.: Delegate and conquer: An LP-based approximation algorithm for minimum degree MSTs. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 169\u2013180. Springer, Heidelberg (2006)"},{"doi-asserted-by":"crossref","unstructured":"Singh, M., Lau, L.C.: Approximating minimum bounded degree spanning trees to within one of optimal. In: Proceedings of the 39th ACM Symposium on Theory of Computing (STOC), pp. 661\u2013670 (2007)","key":"19_CR18","DOI":"10.1145\/1250790.1250887"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-00202-1_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,5]],"date-time":"2019-03-05T07:45:07Z","timestamp":1551771907000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-00202-1_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642002014","9783642002021"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-00202-1_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}