{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T23:05:32Z","timestamp":1746313532387,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":43,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642336508"},{"type":"electronic","value":"9783642336515"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33651-5_11","type":"book-chapter","created":{"date-parts":[[2012,11,13]],"date-time":"2012-11-13T09:25:32Z","timestamp":1352798732000},"page":"151-165","source":"Crossref","is-referenced-by-count":14,"title":["Dense Subgraphs on Dynamic Networks"],"prefix":"10.1007","author":[{"given":"Atish","family":"Das Sarma","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ashwin","family":"Lall","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danupon","family":"Nanongkai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amitabh","family":"Trehan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"Afek, Y., Awerbuch, B., Plotkin, S.A., Saks, M.E.: Local management of a global resource in a communication network. In: FOCS, pp. 347\u2013357. IEEE Computer Society (1987)","DOI":"10.1109\/SFCS.1987.38"},{"key":"11_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1007\/3-540-57529-4_72","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"S. Aggarwal","year":"1993","unstructured":"Aggarwal, S., Kutten, S.: Time Optimal Self-Stabilizing Spanning Tree Algorithms. In: Shyamasundar, R.K. (ed.) FSTTCS 1993. LNCS, vol.\u00a0761, pp. 400\u2013410. Springer, Heidelberg (1993)"},{"key":"11_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/978-3-540-95995-3_3","volume-title":"Algorithms and Models for the Web-Graph","author":"R. Andersen","year":"2009","unstructured":"Andersen, R., Chellapilla, K.: Finding Dense Subgraphs with Size Bounds. In: Avrachenkov, K., Donato, D., Litvak, N. (eds.) WAW 2009. LNCS, vol.\u00a05427, pp. 25\u201337. Springer, Heidelberg (2009)"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Local and global properties in networks of processors (extended abstract). In: Miller, R.E., Ginsburg, S., Burkhard, W.A., Lipton, R.J. (eds.) STOC, pp. 82\u201393. ACM (1980)","DOI":"10.1145\/800141.804655"},{"issue":"1-3","key":"11_CR5","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/S0166-218X(01)00243-8","volume":"121","author":"Y. Asahiro","year":"2002","unstructured":"Asahiro, Y., Hassin, R., Iwama, K.: Complexity of finding dense subgraphs. Discrete Appl. Math.\u00a0121(1-3), 15\u201326 (2002)","journal-title":"Discrete Appl. Math."},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations and Advanced Topics. John Wiley & Sons (2004)","DOI":"10.1002\/0471478210"},{"issue":"5","key":"11_CR7","first-page":"454","volume":"5","author":"B. Bahmani","year":"2012","unstructured":"Bahmani, B., Kumar, R., Vassilvitskii, S.: Densest subgraph in streaming and mapreduce. PVLDB\u00a05(5), 454\u2013465 (2012)","journal-title":"PVLDB"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Berns, A., Ghosh, S.: Dissecting self-* properties. In: International Conference on Self-Adaptive and Self-Organizing Systems, pp. 10\u201319 (2009)","DOI":"10.1109\/SASO.2009.25"},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Vijayaraghavan, A., Guruswami, V., Zhou, Y.: Polynomial integrality gaps for strong sdp relaxations of densest k-subgraph. In: SODA, pp. 388\u2013405 (2012)","DOI":"10.1137\/1.9781611973099.34"},{"key":"11_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/3-540-44436-X_10","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"M. Charikar","year":"2000","unstructured":"Charikar, M.: Greedy Approximation Algorithms for Finding Dense Components in a Graph. In: Jansen, K., Khuller, S. (eds.) APPROX 2000. LNCS, vol.\u00a01913, pp. 84\u201395. Springer, Heidelberg (2000)"},{"issue":"2","key":"11_CR11","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0020-0190(94)00237-S","volume":"54","author":"I. Cidon","year":"1995","unstructured":"Cidon, I., Shavitt, Y.: Message terminating algorithms for anonymous rings of unknown size. Inf. Process. Lett.\u00a054(2), 111\u2013119 (1995)","journal-title":"Inf. Process. Lett."},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"Das Sarma, A., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. In: STOC, pp. 363\u2013372 (2011)","DOI":"10.1145\/1993636.1993686"},{"key":"11_CR13","doi-asserted-by":"crossref","unstructured":"Das Sarma, A., Lall, A., Nanongkai, D., Trehan, A.: Dense subgraphs on dynamic networks. CoRR abs\/1208.1454 (2012)","DOI":"10.1007\/978-3-642-33651-5_11"},{"issue":"11","key":"11_CR14","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1145\/361179.361202","volume":"17","author":"E.W. Dijkstra","year":"1974","unstructured":"Dijkstra, E.W.: Self-stabilizing systems in spite of distributed control. Commun. ACM\u00a017(11), 643\u2013644 (1974), http:\/\/dx.doi.org\/10.1145\/361179.361202","journal-title":"Commun. ACM"},{"key":"11_CR15","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/6156.001.0001","volume-title":"Self-stabilization","author":"S. Dolev","year":"2000","unstructured":"Dolev, S.: Self-stabilization. MIT Press, Cambridge (2000)"},{"key":"11_CR16","unstructured":"Dubhashi, D.P., Grandioni, F., Panconesi, A.: Distributed Algorithms via LP Duality and Randomization. In: Handbook of Approximation Algorithms and Metaheuristics. Chapman and Hall\/CRC (2007)"},{"issue":"4","key":"11_CR17","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1145\/1054916.1054931","volume":"35","author":"M. Elkin","year":"2004","unstructured":"Elkin, M.: An overview of distributed approximation. ACM SIGACT News Distributed Computing Column\u00a035(4), 40\u201357 (2004)","journal-title":"ACM SIGACT News Distributed Computing Column"},{"key":"11_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1007\/978-3-642-04355-0_7","volume-title":"Distributed Computing","author":"Y. Emek","year":"2009","unstructured":"Emek, Y., Korman, A.: New Bounds for the Controller Problem. In: Keidar, I. (ed.) DISC 2009. LNCS, vol.\u00a05805, pp. 22\u201334. Springer, Heidelberg (2009)"},{"key":"11_CR19","doi-asserted-by":"crossref","unstructured":"Feige, U., Kortsarz, G., Peleg, D.: The dense k-subgraph problem. Algorithmica 29 (1999)","DOI":"10.1007\/s004530010050"},{"key":"11_CR20","doi-asserted-by":"crossref","unstructured":"Frischknecht, S., Holzer, S., Wattenhofer, R.: Networks cannot compute their diameter in sublinear time. In: SODA, pp. 1150\u20131162 (2012)","DOI":"10.1137\/1.9781611973099.91"},{"issue":"4","key":"11_CR21","doi-asserted-by":"publisher","first-page":"2164","DOI":"10.1016\/j.dss.2006.06.011","volume":"42","author":"D. Ghosh","year":"2007","unstructured":"Ghosh, D., Sharman, R., Raghav Rao, H., Upadhyaya, S.: Self-healing systems - survey and synthesis. Decis. Support Syst.\u00a042(4), 2164\u20132185 (2007)","journal-title":"Decis. Support Syst."},{"key":"11_CR22","unstructured":"Gibson, D., Kumar, R., Tomkins, A.: Discovering large dense subgraphs in massive graphs. In: B\u00f6hm, K., Jensen, C.S., Haas, L.M., Kersten, M.L., Larson, P.\u00c5., Ooi, B.C. (eds.) VLDB, pp. 721\u2013732. ACM (2005)"},{"key":"11_CR23","unstructured":"Goldberg, A.V.: Finding a maximum density subgraph. Tech. Rep. UCB\/CSD-84-171, EECS Department, University of California, Berkeley (1984)"},{"key":"11_CR24","doi-asserted-by":"crossref","unstructured":"Hayes, T., Saia, J., Trehan, A.: The forgiving graph: a distributed data structure for low stretch under adversarial attack. Distributed Computing, 1\u201318, http:\/\/dx.doi.org\/10.1007\/s00446-012-0160-1 , 10.1007, doi:10.1007\/s00446-012-0160-1","DOI":"10.1007\/s00446-012-0160-1"},{"key":"11_CR25","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1145\/1582716.1582740","volume-title":"PODC 2009: Proceedings of the 28th ACM Symposium on Principles of Distributed Computing","author":"T.P. Hayes","year":"2009","unstructured":"Hayes, T.P., Saia, J., Trehan, A.: The forgiving graph: a distributed data structure for low stretch under adversarial attack. In: PODC 2009: Proceedings of the 28th ACM Symposium on Principles of Distributed Computing, pp. 121\u2013130. ACM, New York (2009)"},{"key":"11_CR26","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/s00446-007-0047-8","volume":"20","author":"M. Khan","year":"2008","unstructured":"Khan, M., Pandurangan, G.: A fast distributed approximation algorithm for minimum spanning trees. Distributed Computing\u00a020, 391\u2013402 (2008)","journal-title":"Distributed Computing"},{"key":"11_CR27","doi-asserted-by":"crossref","unstructured":"Khan, M., Kuhn, F., Malkhi, D., Pandurangan, G., Talwar, K.: Efficient distributed approximation algorithms via probabilistic tree embeddings. In: PODC, pp. 263\u2013272 (2008)","DOI":"10.1145\/1400751.1400787"},{"issue":"4","key":"11_CR28","doi-asserted-by":"publisher","first-page":"1025","DOI":"10.1137\/S0097539705447037","volume":"36","author":"S. Khot","year":"2006","unstructured":"Khot, S.: Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Computing\u00a036(4), 1025\u20131071 (2006)","journal-title":"SIAM J. Computing"},{"key":"11_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/978-3-642-02927-1_50","volume-title":"Automata, Languages and Programming","author":"S. Khuller","year":"2009","unstructured":"Khuller, S., Saha, B.: On Finding Dense Subgraphs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 597\u2013608. Springer, Heidelberg (2009)"},{"key":"11_CR30","doi-asserted-by":"crossref","unstructured":"Korman, A., Kutten, S.: Controller and estimator for dynamic networks. In: Gupta, I., Wattenhofer, R. (eds.) PODC, pp. 175\u2013184. ACM (2007)","DOI":"10.1145\/1281100.1281127"},{"key":"11_CR31","doi-asserted-by":"crossref","unstructured":"Korman, A., Kutten, S., Masuzawa, T.: Fast and compact self stabilizing verification, computation, and fault detection of an MST. In: Gavoille, C., Fraigniaud, P. (eds.) PODC, pp. 311\u2013320. ACM (2011)","DOI":"10.1145\/1993806.1993866"},{"key":"11_CR32","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Lynch, N.A., Oshman, R.: Distributed computation in dynamic networks. In: STOC, pp. 513\u2013522 (2010)","DOI":"10.1145\/1806689.1806760"},{"key":"11_CR33","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Oshman, R., Moses, Y.: Coordinated consensus in dynamic networks. In: PODC, pp. 1\u201310 (2011)","DOI":"10.1145\/1993806.1993808"},{"key":"11_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/11558989_2","volume-title":"Peer-to-Peer Systems IV","author":"F. Kuhn","year":"2005","unstructured":"Kuhn, F., Schmid, S., Wattenhofer, R.: A Self-repairing Peer-to-Peer System Resilient to Dynamic Adversarial Churn. In: van Renesse, R. (ed.) IPTPS 2005. LNCS, vol.\u00a03640, pp. 13\u201323. Springer, Heidelberg (2005)"},{"key":"11_CR35","unstructured":"Lawler, E.: Combinatorial optimization - networks and matroids. Holt, Rinehart, and Winston (1976)"},{"key":"11_CR36","volume-title":"Distributed Algorithms","author":"N. Lynch","year":"1996","unstructured":"Lynch, N.: Distributed Algorithms. Morgan Kaufmann Publishers, San Mateo (1996)"},{"key":"11_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/3-540-51687-5_42","volume-title":"Distributed Algorithms","author":"Y. Matias","year":"1989","unstructured":"Matias, Y., Afek, Y.: Simple and Efficient Election Algorithms for Anonymous Networks. In: Bermond, J.-C., Raynal, M. (eds.) WDAG 1989. LNCS, vol.\u00a0392, pp. 183\u2013194. Springer, Heidelberg (1989)"},{"key":"11_CR38","doi-asserted-by":"crossref","unstructured":"Nanongkai, D., Das Sarma, A., Pandurangan, G.: A tight unconditional lower bound on distributed randomwalk computation. In: PODC, pp. 257\u2013266 (2011)","DOI":"10.1145\/1993806.1993853"},{"key":"11_CR39","doi-asserted-by":"crossref","unstructured":"Pandurangan, G., Khan, M.: Theory of communication networks. In: Algorithms and Theory of Computation Handbook, 2nd edn. CRC Press (2009)","DOI":"10.1201\/9781584888215-c27"},{"key":"11_CR40","unstructured":"Pandurangan, G., Trehan, A.: Xheal: localized self-healing using expanders. In: Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2011, pp. 301\u2013310. ACM (2011), http:\/\/doi.acm.org\/10.1145\/1993806.1993865"},{"key":"11_CR41","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed computing: a locality-sensitive approach. Society for Industrial and Applied Mathematics, Philadelphia (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"11_CR42","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1145\/846057.864027","volume":"1","author":"R. Poor","year":"2003","unstructured":"Poor, R., Bowman, C., Auburn, C.B.: Self-healing networks. Queue\u00a01, 52\u201359 (2003), http:\/\/doi.acm.org\/10.1145\/846057.864027","journal-title":"Queue"},{"key":"11_CR43","unstructured":"Trehan, A.: Algorithms for self-healing networks. Dissertation, University of New Mexico (2010)"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33651-5_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,31]],"date-time":"2022-01-31T05:51:12Z","timestamp":1643608272000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33651-5_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642336508","9783642336515"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33651-5_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}