{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T08:11:43Z","timestamp":1725869503847},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319487489"},{"type":"electronic","value":"9783319487496"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-319-48749-6_14","type":"book-chapter","created":{"date-parts":[[2016,10,30]],"date-time":"2016-10-30T04:16:59Z","timestamp":1477801019000},"page":"187-201","source":"Crossref","is-referenced-by-count":0,"title":["Constant Factor Approximation for the Weighted Partial Degree Bounded Edge Packing Problem"],"prefix":"10.1007","author":[{"given":"Pawan","family":"Aurora","sequence":"first","affiliation":[]},{"given":"Monalisa","family":"Jena","sequence":"additional","affiliation":[]},{"given":"Rajiv","family":"Raman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,10,31]]},"reference":[{"key":"14_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1007\/3-540-62592-5_80","volume-title":"Algorithms and Complexity","author":"P Alimonti","year":"1997","unstructured":"Alimonti, P., Kann, V.: Hardness of approximating problems on cubic graphs. In: Bongiovanni, G., Bovet, D.P., Di Battista, G. (eds.) CIAC 1997. LNCS, vol. 1203, pp. 288\u2013298. Springer, Heidelberg (1997)"},{"key":"14_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1007\/978-3-642-38756-2_6","volume-title":"Frontiers in Algorithmics and Algorithmic Aspects in Information and Management","author":"P Aurora","year":"2013","unstructured":"Aurora, P., Singh, S., Mehta, S.K.: Partial degree bounded edge packing problem with arbitrary bounds. In: Tan, X., Zhu, B., Fellows, M. (eds.) FAW-AAIM 2013. LNCS, vol. 7924, pp. 24\u201335. Springer, Heidelberg (2013)"},{"key":"14_CR3","unstructured":"Babenko, M.A., Gusakov, A.: New exact and approximation algorithms for the star packing problem in undirected graphs. In: 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, 10\u201312 March 2011, Dortmund, Germany, pp. 519\u2013530 (2011)"},{"issue":"1","key":"14_CR4","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153\u2013180 (1994)","journal-title":"J. ACM"},{"issue":"1\u20132","key":"14_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209(1\u20132), 1\u201345 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"14_CR6","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1016\/j.tcs.2014.09.039","volume":"562","author":"T-M Bu","year":"2015","unstructured":"Bu, T.-M., Yuan, C., Zhang, P.: Computing on binary strings. Theoret. Comput. Sci. 562, 122\u2013128 (2015)","journal-title":"Theoret. Comput. Sci."},{"issue":"11","key":"14_CR7","doi-asserted-by":"crossref","first-page":"1264","DOI":"10.1016\/j.ic.2008.07.003","volume":"206","author":"M Chleb\u00edk","year":"2008","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Approximation hardness of dominating set problems in bounded degree graphs. Inf. Comput. 206(11), 1264\u20131275 (2008)","journal-title":"Inf. Comput."},{"key":"14_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/11611257_21","volume-title":"SOFSEM 2006: Theory and Practice of Computer Science","author":"F Dehne","year":"2006","unstructured":"Dehne, F., Fellows, M.R., Fernau, H., Prieto, E., Rosamond, F.A.: nonblocker: parameterized algorithmics for minimum dominating set. In: Wiedermann, J., Tel, G., Pokorn\u00fd, J., Bielikov\u00e1, M., \u0160tuller, J. (eds.) SOFSEM 2006. LNCS, vol. 3831, pp. 237\u2013245. Springer, Heidelberg (2006)"},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Hajiaghayi, M.T., Kawarabayashi, K.-i.: Algorithmic graph minor theory: decomposition, approximation, and coloring. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23\u201325 October 2005, Pittsburgh, PA, USA, pp. 637\u2013646 (2005)","DOI":"10.1109\/SFCS.2005.14"},{"issue":"3","key":"14_CR10","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17(3), 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"key":"14_CR11","series-title":"The IBM Research Symposia Series","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D., et al. (eds.) Complexity of Computer Computations. The IBM Research Symposia Series, pp. 85\u2013103. Springer, Heidelberg (1972)"},{"key":"14_CR12","doi-asserted-by":"crossref","DOI":"10.1090\/chel\/367","volume-title":"Matching Theory","author":"L Lov\u00e1sz","year":"2009","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory, vol. 367. American Mathematical Soc., Providence (2009)"},{"key":"14_CR13","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An $${O}(\\sqrt{|{V}|}|{E}|)$$ algoithm for finding maximum matching in general graphs. In: 21st Annual Symposium on Foundations of Computer Science, pp. 17\u201327. IEEE (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"14_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/978-3-642-20807-2_28","volume-title":"Integer Programming and Combinatoral Optimization","author":"O Parekh","year":"2011","unstructured":"Parekh, O.: Iterative packing for demand and hypergraph matching. In: G\u00fcnl\u00fck, O., Woeginger, G.J. (eds.) IPCO 2011. LNCS, vol. 6655, pp. 349\u2013361. Springer, Heidelberg (2011)"},{"key":"14_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/978-3-319-18263-6_18","volume-title":"Approximation and Online Algorithms","author":"O Parekh","year":"2015","unstructured":"Parekh, O., Pritchard, D.: Generalized hypergraph matching via iterated packing and local ratio. In: Bampis, E., Svensson, O. (eds.) WAOA 2014. LNCS, vol. 8952, pp. 207\u2013223. Springer, Heidelberg (2015)"},{"key":"14_CR16","unstructured":"Sahni, S.K.: On the knapsack and other computationally related problems (1973)"},{"key":"14_CR17","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol. 24. Springer Science & Business Media, Heidelberg (2003)"},{"key":"14_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1007\/3-540-47867-1_32","volume-title":"Integer Programming and Combinatorial Optimization","author":"B Shepherd","year":"2002","unstructured":"Shepherd, B., Vetta, A.: The demand matching problem. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol. 2337, pp. 457\u2013474. Springer, Heidelberg (2002)"},{"key":"14_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/978-3-642-29700-7_33","volume-title":"Frontiers in Algorithmics and Algorithmic Aspects in Information and Management","author":"P Zhang","year":"2012","unstructured":"Zhang, P.: Partial degree bounded edge packing problem. In: Snoeyink, J., Lu, P., Su, K., Wang, L. (eds.) AAIM 2012 and FAW 2012. LNCS, vol. 7285, pp. 359\u2013367. Springer, Heidelberg (2012)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-48749-6_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,15]],"date-time":"2019-09-15T00:40:46Z","timestamp":1568508046000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-48749-6_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319487489","9783319487496"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-48749-6_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}