{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:28:45Z","timestamp":1758270525733,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"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_58","type":"book-chapter","created":{"date-parts":[[2015,9,1]],"date-time":"2015-09-01T01:40:34Z","timestamp":1441071634000},"page":"693-704","source":"Crossref","is-referenced-by-count":6,"title":["Approximation Algorithms for Connected Maximum Cut and Related Problems"],"prefix":"10.1007","author":[{"given":"Mohammad Taghi","family":"Hajiaghayi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"MacDavid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manish","family":"Purohit","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kanthi","family":"Sarpatwar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,12]]},"reference":[{"key":"58_CR1","doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A., Vondr\u00e1k, J.: Fast algorithms for maximizing submodular functions. In: SODA, pp. 1497\u20131514 (2014)","DOI":"10.1137\/1.9781611973402.110"},{"key":"58_CR2","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Naor, J., Schwartz, R.: A tight linear time (1\/2)-approximation for unconstrained submodular maximization. In: FOCS, pp. 649\u2013658 (2012)","DOI":"10.1109\/FOCS.2012.73"},{"key":"58_CR3","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Naor, J., Schwartz, R.: Submodular maximization with cardinality constraints. In: SODA, pp. 1433\u20131452 (2014)","DOI":"10.1137\/1.9781611973402.106"},{"key":"58_CR4","doi-asserted-by":"crossref","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a submodular set function subject to a matroid constraint. In: IPCO, pp. 182\u2013196 (2007)","DOI":"10.1007\/978-3-540-72792-7_15"},{"key":"58_CR5","doi-asserted-by":"crossref","unstructured":"Censor-Hillel, K., Ghaffari, M., Giakkoupis, G., Haeupler, B., Kuhn, F.: Tight bounds on vertex connectivity under vertex sampling. In: SODA (2015)","DOI":"10.1137\/1.9781611973730.133"},{"key":"58_CR6","doi-asserted-by":"crossref","unstructured":"Censor-Hillel, K., Ghaffari, M., Kuhn, F.: A new perspective on vertex connectivity. In: SODA, pp. 546\u2013561 (2014)","DOI":"10.1137\/1.9781611973402.41"},{"key":"58_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/978-3-642-22006-7_30","volume-title":"Automata, Languages and Programming","author":"C. Chekuri","year":"2011","unstructured":"Chekuri, C., Ene, A.: Submodular Cost Allocation Problem and Applications. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol.\u00a06755, pp. 354\u2013366. Springer, Heidelberg (2011)"},{"key":"58_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/978-3-642-31155-0_9","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"M. Cygan","year":"2012","unstructured":"Cygan, M.: Deterministic parameterized connected vertex cover. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol.\u00a07357, pp. 95\u2013106. Springer, Heidelberg (2012)"},{"key":"58_CR9","doi-asserted-by":"crossref","unstructured":"Das, B., Bharghavan, V.: Routing in ad-hoc networks using minimum connected dominating sets. In: ICC, vol.\u00a01, pp. 376\u2013380 (1997)","DOI":"10.1109\/ICC.1997.605303"},{"key":"58_CR10","unstructured":"de Berg, M., Khosravi, A.: Finding perfect auto-partitions is NP-hard. In: EuroCG 2008, pp. 255\u2013258 (2008)"},{"key":"58_CR11","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Hajiaghayi, M., Kawarabayashi, K.-I.: Contraction decomposition in H-minor-free graphs and algorithmic applications. In: STOC, pp. 441\u2013450 (2011)","DOI":"10.1145\/1993636.1993696"},{"key":"58_CR12","doi-asserted-by":"crossref","unstructured":"Du, D.Z., Wan, P.J.: Connected dominating set: theory and applications. Springer optimization and its applications (2013)","DOI":"10.1007\/978-1-4614-5242-3"},{"key":"58_CR13","unstructured":"Eisenbrand, F., Grandoni, F., Rothvo\u00df, T., Sch\u00e4fer, G.: Approximating connected facility location problems via random facility sampling and core detouring. In: SODA, pp. 1174\u20131183 (2008)"},{"key":"58_CR14","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: STOC, pp. 448\u2013455 (2003)","DOI":"10.1145\/780542.780608"},{"issue":"4","key":"58_CR15","doi-asserted-by":"publisher","first-page":"1133","DOI":"10.1137\/090779346","volume":"40","author":"U. Feige","year":"2011","unstructured":"Feige, U., Mirrokni, V.S., Vondrak, J.: Maximizing non-monotone submodular functions. SIAM Journal on Computing\u00a040(4), 1133\u20131153 (2011)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"58_CR16","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1023\/B:VISI.0000022288.19776.77","volume":"59","author":"P.F. Felzenszwalb","year":"2004","unstructured":"Felzenszwalb, P.F., Huttenlocher, D.P.: Efficient graph-based image segmentation. International Journal of Computer Vision\u00a059(2), 167\u2013181 (2004)","journal-title":"International Journal of Computer Vision"},{"key":"58_CR17","unstructured":"Garg, N., Konjevod, G., Ravi, R.: A polylogarithmic approximation algorithm for the group Steiner tree problem. In: SODA, pp. 253\u2013259 (1998)"},{"issue":"6","key":"58_CR18","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM\u00a042(6), 1115\u20131145 (1995)","journal-title":"Journal of the ACM"},{"issue":"4","key":"58_CR19","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/PL00009201","volume":"20","author":"S. Guha","year":"1998","unstructured":"Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica\u00a020(4), 374\u2013387 (1998)","journal-title":"Algorithmica"},{"issue":"3","key":"58_CR20","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1137\/0204019","volume":"4","author":"F. Hadlock","year":"1975","unstructured":"Hadlock, F.: Finding a maximum cut of a planar graph in polynomial time. SIAM Journal on Computing\u00a04(3), 221\u2013225 (1975)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"58_CR21","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1109\/12.67327","volume":"40","author":"D.J. Haglin","year":"1991","unstructured":"Haglin, D.J., Venkatesan, S.M.: Approximation and intractability results for the maximum cut problem and its variants. IEEE Transactions on Computers\u00a040(1), 110\u2013113 (1991)","journal-title":"IEEE Transactions on Computers"},{"key":"58_CR22","unstructured":"Hajiaghayi, M.T., Kortsarz, G., MacDavid, R., Purohit, M., Sarpatwar, K.: Approximation algorithms for connected maximum cut and related problems. CoRR (2015), http:\/\/arxiv.org\/abs\/1507.00648"},{"issue":"1","key":"58_CR23","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1137\/S0097539705447372","volume":"37","author":"S. Khot","year":"2007","unstructured":"Khot, S., Kindler, G., Mossel, E., O\u2019Donnell, R.: Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM Journal on Computing\u00a037(1), 319\u2013357 (2007)","journal-title":"SIAM Journal on Computing"},{"key":"58_CR24","doi-asserted-by":"crossref","unstructured":"Khuller, S., Purohit, M., Sarpatwar, K.K.: Analyzing the optimal neighborhood: Algorithms for budgeted and partial connected dominating set problems. In: SODA, pp. 1702\u20131713 (2014)","DOI":"10.1137\/1.9781611973402.123"},{"key":"58_CR25","doi-asserted-by":"crossref","unstructured":"Kuo, T.-W., Lin, K.C.-J., Tsai, M.-J.: Maximizing submodular set function with connectivity constraint: theory and application to networks. In: INFOCOM, pp. 1977\u20131985 (2013)","DOI":"10.1109\/INFCOM.2013.6566998"},{"key":"58_CR26","doi-asserted-by":"crossref","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press (1995)","DOI":"10.1017\/CBO9780511814075"},{"issue":"1","key":"58_CR27","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"G.L. Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions-I. Mathematical Programming\u00a014(1), 265\u2013294 (1978)","journal-title":"Mathematical Programming"},{"key":"58_CR28","unstructured":"Slav Petrov. Image segmentation with maximum cuts (2005)"},{"key":"58_CR29","doi-asserted-by":"crossref","unstructured":"R\u00e4cke, H.: Optimal hierarchical decompositions for congestion minimization in networks. In: STOC, pp. 255\u2013264 (2008)","DOI":"10.1145\/1374376.1374415"},{"key":"58_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1007\/3-540-68530-8_37","volume-title":"Algorithms - ESA \u201998","author":"R. Solis-Oba","year":"1998","unstructured":"Solis-Oba, R.: 2-Approximation algorithm for finding a spanning tree with maximum number of leaves. In: Bilardi, G., Pietracaprina, A., Italiano, G.F., Pucci, G. (eds.) ESA 1998. LNCS, vol.\u00a01461, pp. 441\u2013452. Springer, Heidelberg (1998)"},{"issue":"4","key":"58_CR31","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00453-004-1112-3","volume":"40","author":"C. Swamy","year":"2004","unstructured":"Swamy, C., Kumar, A.: Primal\u2013dual algorithms for connected facility location problems. Algorithmica\u00a040(4), 245\u2013269 (2004)","journal-title":"Algorithmica"},{"key":"58_CR32","doi-asserted-by":"crossref","unstructured":"Vicente, S., Kolmogorov, V., Rother, C.: Graph cut based image segmentation with connectivity priors. In: CVPR, pp. 1\u20138 (2008)","DOI":"10.1109\/CVPR.2008.4587440"}],"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_58","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T09:56:31Z","timestamp":1748598991000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48350-3_58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662483497","9783662483503"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48350-3_58","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}