{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:02Z","timestamp":1740122402111,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,11,16]],"date-time":"2017-11-16T00:00:00Z","timestamp":1510790400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"TCS Scholarship"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s10878-017-0206-1","type":"journal-article","created":{"date-parts":[[2017,11,16]],"date-time":"2017-11-16T12:54:23Z","timestamp":1510836863000},"page":"1243-1261","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Constant factor approximation for the weighted partial degree bounded edge packing problem"],"prefix":"10.1007","volume":"36","author":[{"given":"Pawan","family":"Aurora","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7431-2814","authenticated-orcid":false,"given":"Monalisa","family":"Jena","sequence":"additional","affiliation":[]},{"given":"Rajiv","family":"Raman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,11,16]]},"reference":[{"key":"206_CR1","doi-asserted-by":"crossref","unstructured":"Alimonti P, Kann V (1997) Hardness of approximating problems on cubic graphs. In: Proceedings of the third Italian conference on algorithms and complexity, CIAC \u201997, Rome, Italy, March 12\u201314, pp 288\u2013298","DOI":"10.1007\/3-540-62592-5_80"},{"key":"206_CR2","doi-asserted-by":"publisher","unstructured":"Aurora P, Singh S, Mehta SK (2013) Partial degree bounded edge packing problem with arbitrary bounds. In: Proceedings of the joint international conference on frontiers in algorithmics and algorithmic aspects in information and management, FAW-AAIM 2013, Dalian, China, June 26\u201328, 2013, pp 24\u201335. https:\/\/doi.org\/10.1007\/978-3-642-38756-2_6","DOI":"10.1007\/978-3-642-38756-2_6"},{"key":"206_CR3","unstructured":"Babenko M, Gusakov A (2011) 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, March 10\u201312, Dortmund, Germany, pp 519\u2013530"},{"issue":"1","key":"206_CR4","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker BS (1994) Approximation algorithms for NP-complete problems on planar graphs. J ACM 41(1):153\u2013180","journal-title":"J ACM"},{"issue":"1\u20132","key":"206_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 HL (1998) A partial k-arboretum of graphs with bounded treewidth. Theor Comput Sci 209(1\u20132):1\u201345","journal-title":"Theor Comput Sci"},{"key":"206_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 (2015) Computing on binary strings. Theor Comput Sci 562:122\u2013128","journal-title":"Theor Comput Sci"},{"key":"206_CR7","doi-asserted-by":"crossref","unstructured":"Crescenzi P (1997) A short guide to approximation preserving reductions. In: Proceedings of the twelfth annual IEEE conference on computational complexity, Ulm, Germany, June 24\u201327, pp 262\u2013273","DOI":"10.1109\/CCC.1997.612321"},{"key":"206_CR8","unstructured":"Dehne FKHA, Fellows MR, Fernau H, Prieto E, Rosamond FA (2006) NONBLOCKER: parameterized algorithmics for minimum dominating set. In: Proceedings of the 32nd conference on current trends in theory and practice of computer science, SOFSEM 2006: theory and practice of computer science, Mer\u00edn, Czech Republic, January 21\u201327, pp 237\u2013245"},{"key":"206_CR9","doi-asserted-by":"crossref","unstructured":"Demaine ED, Hajiaghayi MT, Kawarabayashi K-I (2005) 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","DOI":"10.1109\/SFCS.2005.14"},{"issue":"3","key":"206_CR10","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"Jack Edmonds","year":"1965","unstructured":"Edmonds Jack (1965) Paths, trees, and flowers. Can J Math 17(3):449\u2013467","journal-title":"Can J Math"},{"key":"206_CR11","unstructured":"Jukka S (2010) ( https:\/\/cstheory.stackexchange.com\/users\/74\/jukka suomela ). Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete? Theoretical computer science stack exchange. https:\/\/cstheory.stackexchange.com\/q\/2508 (version: 2010-11-01)"},{"key":"206_CR12","volume-title":"Reducibility among combinatorial problems","author":"RM Karp","year":"1972","unstructured":"Karp RM (1972) Reducibility among combinatorial problems. Springer, Berlin"},{"key":"206_CR13","volume-title":"Matching theory","author":"L Lov\u00e1sz","year":"2009","unstructured":"Lov\u00e1sz L, Plummer MD (2009) Matching theory, vol 367. American Mathematical Society, Providence"},{"key":"206_CR14","unstructured":"Micali S, Vazirani VV (1980) An $${O}(\\sqrt{|{V}|}|{E}|)$$ O ( | V | | E | ) algoithm for finding maximum matching in general graphs. In: 21st annual Symposium on foundations of computer science. IEEE, pp 17\u201327"},{"key":"206_CR15","doi-asserted-by":"crossref","unstructured":"Parekh O (2011) Iterative packing for demand and hypergraph matching. In: G\u00fcnl\u00fck O, Woeginger GJ (eds) Integer programming and combinatoral optimization. Springer, pp 349\u2013361","DOI":"10.1007\/978-3-642-20807-2_28"},{"key":"206_CR16","unstructured":"Parekh O, Pritchard D (2014) Generalized hypergraph matching via iterated packing and local ratio. In: Bampis E, Svensson O (eds) Approximation and online algorithms. Springer, pp 207\u2013223"},{"key":"206_CR17","unstructured":"Sahni SK(1973) On the knapsack and other computationally related problems. Ph.D. Dissertation, Cornell University"},{"key":"206_CR18","volume-title":"Combinatorial optimization: polyhedra and efficiency","author":"Alexander Schrijver","year":"2003","unstructured":"Schrijver Alexander (2003) Combinatorial optimization: polyhedra and efficiency, vol 24. Springer, Berlin"},{"key":"206_CR19","doi-asserted-by":"crossref","unstructured":"Shepherd FB, Vetta A (2002) The demand matching problem. In: Proceedings of the 9th international IPCO conference on integer programming and combinatorial optimization, Cambridge, MA, USA, May 27\u201329, pp 457\u2013474","DOI":"10.1007\/3-540-47867-1_32"},{"key":"206_CR20","doi-asserted-by":"crossref","unstructured":"Zhang P (2012) Partial degree bounded edge packing problem. In: Proceedings of the joint international conference on frontiers in algorithmics and algorithmic aspects in information and management, FAW-AAIM 2012, Beijing, China, May 14\u201316, pp 359\u2013367","DOI":"10.1007\/978-3-642-29700-7_33"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-017-0206-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0206-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0206-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,6]],"date-time":"2019-10-06T03:27:38Z","timestamp":1570332458000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-017-0206-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,16]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["206"],"URL":"https:\/\/doi.org\/10.1007\/s10878-017-0206-1","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2017,11,16]]}}}