{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T20:48:11Z","timestamp":1725828491973},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662483497"},{"type":"electronic","value":"9783662483503"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-662-48350-3_79","type":"book-chapter","created":{"date-parts":[[2015,8,31]],"date-time":"2015-08-31T21:40:34Z","timestamp":1441057234000},"page":"953-964","source":"Crossref","is-referenced-by-count":2,"title":["Improved Approximation Algorithms for Weighted 2-Path Partitions"],"prefix":"10.1007","author":[{"given":"Amotz","family":"Bar-Noy","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"George","family":"Rabanca","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ivo","family":"Vigan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,12]]},"reference":[{"issue":"3","key":"79_CR1","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1287\/moor.23.3.640","volume":"23","author":"E. Arkin","year":"1998","unstructured":"Arkin, E., Hassin, R.: On local search for weighted k-set packing. Math. Operations Research\u00a023(3), 640\u2013648 (1998)","journal-title":"Math. Operations Research"},{"key":"79_CR2","unstructured":"Babenko, M., Gusakov, A.: New exact and approximation algorithms for the star packing problem in undirected graphs. In: STACS, pp. 519\u2013530 (2011)"},{"key":"79_CR3","unstructured":"Bar-Noy, A., Basu, P., Baumer, B., Rabanca, G.: Star search: Effective subgroups in collaborative social networks (unpublished)"},{"key":"79_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/978-3-540-68880-8_11","volume-title":"Algorithmic Aspects in Information and Management","author":"Z.-Z. Chen","year":"2008","unstructured":"Chen, Z.-Z., Tanahashi, R., Wang, L.: An improved randomized approximation algorithm for maximum triangle packing. In: Fleischer, R., Xu, J. (eds.) AAIM 2008. LNCS, vol.\u00a05034, pp. 97\u2013108. Springer, Heidelberg (2008)"},{"issue":"7","key":"79_CR5","doi-asserted-by":"publisher","first-page":"1640","DOI":"10.1016\/j.dam.2008.11.009","volume":"157","author":"Z.Z. Chen","year":"2009","unstructured":"Chen, Z.Z., Tanahashi, R., Wang, L.: An improved randomized approximation algorithm for maximum triangle packing. Discrete Applied Mathematics\u00a0157(7), 1640 (2009)","journal-title":"Discrete Applied Mathematics"},{"key":"#cr-split#-79_CR6.1","doi-asserted-by":"crossref","unstructured":"Chen, Z.Z., Tanahashi, R., Wang, L.: Erratum to, An improved randomized approximation algorithm for maximum triangle packing. Discrete Appl. Math.\u00a0157 (2009)","DOI":"10.1016\/j.dam.2008.11.009"},{"key":"#cr-split#-79_CR6.2","doi-asserted-by":"crossref","unstructured":"Discrete Applied Mathematics 158(9), 1045-1047 (2010)","DOI":"10.1016\/j.dam.2010.01.011"},{"key":"79_CR7","series-title":"LNCS","first-page":"152","volume-title":"ISAAC","author":"M. Chleb\u00eck","year":"2003","unstructured":"Chleb\u00eck, M., Chleb\u00eckov\u00e1, J.: Approximation hardness fo2653r small occurrence instances of NP-hard problems. In: Petreschi, R., Persiano, G., Silvestri, R. (eds.) ISAAC. LNCS, vol.\u00a02653, pp. 152\u2013164. Springer, Heidelberg (2003)"},{"issue":"2","key":"79_CR8","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1145\/321941.321942","volume":"23","author":"H. Gabow","year":"1976","unstructured":"Gabow, H.: An efficient implementation of Edmonds\u2019 algorithm for maximum matching on graphs. J. ACM\u00a023(2), 221\u2013234 (1976)","journal-title":"J. ACM"},{"key":"79_CR9","doi-asserted-by":"crossref","unstructured":"Gajewar, A., Sarma, A.S.: Multi-skill collaborative teams based on densest subgraphs. In: SDM, pp. 165\u2013176. SIAM\/Omnipress (2012)","DOI":"10.1137\/1.9781611972825.15"},{"key":"79_CR10","volume-title":"Computers and Intractability: a Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)"},{"key":"79_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/10692760_3","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"V. Guruswami","year":"1998","unstructured":"Guruswami, V., Pandu Rangan, C., Chang, M.S., Chang, G.J., Wong, C.K.: The vertex-disjoint triangles problem. In: Hromkovi\u010d, J., S\u00fdkora, O. (eds.) WG 1998. LNCS, vol.\u00a01517, pp. 26\u201337. Springer, Heidelberg (1998)"},{"key":"79_CR12","unstructured":"Halld\u00f3rsson, M.: Approximating discrete collections via local improvements. In: SODA, pp. 160\u2013169 (1995)"},{"key":"79_CR13","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/S0020-0190(97)00097-5","volume":"63","author":"R. Hassin","year":"1997","unstructured":"Hassin, R., Rubinstein, S.: An approximation algorithm for maximum packing of 3-edge paths. Information Processing Letters\u00a063, 63\u201367 (1997)","journal-title":"Information Processing Letters"},{"issue":"6","key":"79_CR14","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1016\/j.dam.2005.11.003","volume":"154","author":"R. Hassin","year":"2006","unstructured":"Hassin, R., Rubinstein, S.: An approximation algorithm for maximum triangle packing. Discrete Applied Math.\u00a0154(6), 971\u2013979 (2006)","journal-title":"Discrete Applied Math."},{"key":"#cr-split#-79_CR15.1","doi-asserted-by":"crossref","unstructured":"Hassin, R., Rubinstein, S.: Erratum to \"An approximation algorithm for maximum triangle packing\". Discrete Applied Math.\u00a0154, 971-979 (2006)","DOI":"10.1016\/j.dam.2005.11.003"},{"key":"#cr-split#-79_CR15.2","doi-asserted-by":"crossref","unstructured":"Discrete Applied Math. 154(18), 2620 (2006)","DOI":"10.1016\/j.dam.2006.05.005"},{"issue":"4","key":"79_CR16","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/j.disopt.2013.09.001","volume":"10","author":"R. Hassin","year":"2013","unstructured":"Hassin, R., Schneider, O.: A local search algorithm for binary maximum 2-path partitioning. Discrete Optimization\u00a010(4), 333\u2013360 (2013)","journal-title":"Discrete Optimization"},{"issue":"2","key":"79_CR17","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1137\/0607024","volume":"7","author":"P. Hell","year":"1986","unstructured":"Hell, P., Kirkpatrick, D.C.: Packings by complete bipartite graphs. SIAM J. Algebraic Discrete Methods\u00a07(2), 199\u2013209 (1986)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"1","key":"79_CR18","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0402008","volume":"2","author":"C.A.J. Hurkens","year":"1989","unstructured":"Hurkens, C.A.J., Schrijver, A.: On the size of systems of sets every t of which have an sdr, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Discrete Math.\u00a02(1), 68\u201372 (1989)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"79_CR19","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0020-0190(91)90246-E","volume":"37","author":"V. Kann","year":"1991","unstructured":"Kann, V.: Maximum bounded 3-dimensional matching is MAX SNP-complete. Information Processing Letters\u00a037(1), 27\u201335 (1991)","journal-title":"Information Processing Letters"},{"key":"79_CR20","doi-asserted-by":"crossref","unstructured":"Kargar, M., An, A.: Discovering top-k teams of experts with\/without a leader in social networks. In: CIKM, pp. 985\u2013994 (2011)","DOI":"10.1145\/2063576.2063718"},{"key":"79_CR21","doi-asserted-by":"crossref","unstructured":"Li, C.T., Shan, M.K.: Team formation for generalized tasks in expertise social networks. In: SOCIALCOM, pp. 9\u201316 (2010)","DOI":"10.1109\/SocialCom.2010.12"},{"issue":"2","key":"79_CR22","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0166-218X(95)00107-3","volume":"70","author":"Z. Lonc","year":"1996","unstructured":"Lonc, Z.: On the complexity of some edge-partition problems for graphs. Discrete Applied Mathematics\u00a070(2), 177\u2013183 (1996)","journal-title":"Discrete Applied Mathematics"},{"issue":"8","key":"79_CR23","doi-asserted-by":"publisher","first-page":"1455","DOI":"10.1016\/j.disc.2007.07.100","volume":"308","author":"G. Manic","year":"2008","unstructured":"Manic, G., Wakabayashi, Y.: Packing triangles in low degree graphs and indifference graphs. Discrete Math.\u00a0308(8), 1455\u20131471 (2008)","journal-title":"Discrete Math."},{"issue":"3","key":"79_CR24","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1016\/j.tcs.2005.10.009","volume":"351","author":"E. Prieto","year":"2006","unstructured":"Prieto, E., Sloper, C.: Looking at the stars. Theoretical Computer Science\u00a0351(3), 437\u2013445 (2006)","journal-title":"Theoretical Computer Science"},{"key":"79_CR25","doi-asserted-by":"crossref","unstructured":"Rangapuram, S., B\u00fchler, T., Hein, M.: Towards realistic team formation in social networks based on densest subgraphs. In: WWW, pp. 1077\u20131088 (2013)","DOI":"10.1145\/2488388.2488482"},{"key":"79_CR26","doi-asserted-by":"crossref","unstructured":"Tanahashi, R., Chen, Z.: A deterministic approximation algorithm for maximum 2-path packing. IEICE Tr. Inform. & Syst. E93-D(2), 241\u2013249 (2010)","DOI":"10.1587\/transinf.E93.D.241"},{"key":"79_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/978-3-642-14031-0_9","volume-title":"Computing and Combinatorics","author":"A. Zuylen van","year":"2010","unstructured":"van Zuylen, A.: Multiplying pessimistic estimators: deterministic approximation of max TSP and maximum triangle packing. In: Thai, M.T., Sahni, S. (eds.) COCOON 2010. LNCS, vol.\u00a06196, pp. 60\u201369. Springer, Heidelberg (2010)"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2015"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48350-3_79","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T16:20:02Z","timestamp":1559233202000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48350-3_79"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662483497","9783662483503"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48350-3_79","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}