{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T09:38:55Z","timestamp":1649065135128},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,8,1]],"date-time":"2017-08-01T00:00:00Z","timestamp":1501545600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Soc. Netw. Anal. Min."],"published-print":{"date-parts":[[2017,12]]},"DOI":"10.1007\/s13278-017-0457-y","type":"journal-article","created":{"date-parts":[[2017,8,1]],"date-time":"2017-08-01T14:26:20Z","timestamp":1501597580000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Incremental maintenance of all-pairs shortest paths in relational DBMSs"],"prefix":"10.1007","volume":"7","author":[{"given":"Sergio","family":"Greco","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cristian","family":"Molinaro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chiara","family":"Pulice","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ximena","family":"Quintana","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,8,1]]},"reference":[{"key":"457_CR1","doi-asserted-by":"crossref","unstructured":"Akiba T, Iwata Y, Yoshida Y (2013) Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In: Proceeding of international conference on management of data (SIGMOD), pp 349\u2013360","DOI":"10.1145\/2463676.2465315"},{"key":"457_CR2","unstructured":"Baswana S, Hariharan R, Sen S (2003) Maintaining all-pairs approximate shortest paths under deletion of edges. In: Proceedings of ACM-SIAM symposium on discrete algorithms (SODA), pp 394\u2013403"},{"key":"457_CR3","doi-asserted-by":"crossref","unstructured":"Bernstein A (2013) Maintaining shortest paths under deletions in weighted directed graphs: (extended abstract). In: Proceedings of ACM on symposium on theory of computing (STOC), pp 725\u2013734","DOI":"10.1145\/2488608.2488701"},{"key":"457_CR4","doi-asserted-by":"crossref","unstructured":"Bouros P, Skiadopoulos S, Dalamagas T, Sacharidis D, Sellis T.K (2009) Evaluating reachability queries over path collections. In: Proceedings of international conference on scientific and statistical database management (SSDBM), pp 398\u2013416","DOI":"10.1007\/978-3-642-02279-1_29"},{"issue":"6","key":"457_CR5","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1007\/s00778-012-0274-x","volume":"21","author":"L Chang","year":"2012","unstructured":"Chang L, Yu JX, Qin L, Cheng H, Qiao M (2012) The exact distance to destination in undirected world. VLDB J 21(6):869\u2013888","journal-title":"VLDB J"},{"key":"457_CR6","doi-asserted-by":"crossref","unstructured":"Cheng J, Ke Y, Chu S, Cheng C (2012) Efficient processing of distance queries in large graphs: a vertex cover approach. In: Proceedings of international conference on management of data (SIGMOD), pp 457\u2013468","DOI":"10.1145\/2213836.2213888"},{"key":"457_CR7","doi-asserted-by":"crossref","unstructured":"Crecelius T, Schenkel R (2012) Pay-as-you-go maintenance of precomputed nearest neighbors in large graphs. In: Proceedings of ACM conference on information and knowledge management (CIKM), pp 952\u2013961","DOI":"10.1145\/2396761.2396881"},{"issue":"4","key":"457_CR8","doi-asserted-by":"crossref","first-page":"1210","DOI":"10.1016\/j.jnca.2011.06.001","volume":"35","author":"A Cuzzocrea","year":"2012","unstructured":"Cuzzocrea A, Papadimitriou A, Katsaros D, Manolopoulos Y (2012) Edge betweenness centrality: a novel algorithm for qos-based topology control over wireless sensor networks. J Netw Comput Appl 35(4):1210\u20131217","journal-title":"J Netw Comput Appl"},{"key":"457_CR9","unstructured":"Demetrescu C, Emiliozzi S, Italiano G.F (2004) Experimental analysis of dynamic all pairs shortest path algorithms. In: Proceedings of ACM-SIAM symposium on discrete algorithms (SODA), pp 369\u2013378"},{"issue":"6","key":"457_CR10","doi-asserted-by":"crossref","first-page":"968","DOI":"10.1145\/1039488.1039492","volume":"51","author":"C Demetrescu","year":"2004","unstructured":"Demetrescu C, Italiano GF (2004) A new approach to dynamic all pairs shortest paths. J ACM 51(6):968\u2013992","journal-title":"J ACM"},{"issue":"4","key":"457_CR11","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1145\/1198513.1198519","volume":"2","author":"C Demetrescu","year":"2006","unstructured":"Demetrescu C, Italiano GF (2006) Experimental analysis of dynamic all pairs shortest path algorithms. ACM Trans Algorithms 2(4):578\u2013601","journal-title":"ACM Trans Algorithms"},{"issue":"1","key":"457_CR12","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra EW (1959) A note on two problems in connexion with graphs. Numerische Mathematik 1(1):269\u2013271","journal-title":"Numerische Mathematik"},{"issue":"1","key":"457_CR13","doi-asserted-by":"crossref","first-page":"264","DOI":"10.14778\/1920841.1920878","volume":"3","author":"W Fan","year":"2010","unstructured":"Fan W, Li J, Ma S, Tang N, Wu Y, Wu Y (2010) Graph pattern matching: from intractable to polynomial time. Proc VLDB Endow (PVLDB) 3(1):264\u2013275","journal-title":"Proc VLDB Endow (PVLDB)"},{"issue":"6","key":"457_CR14","doi-asserted-by":"crossref","first-page":"457","DOI":"10.14778\/2536336.2536346","volume":"6","author":"AWC Fu","year":"2013","unstructured":"Fu AWC, Wu H, Cheng J, Wong RCW (2013) Is-label: an independent-set based labeling scheme for point-to-point distance querying. Proc VLDB Endow (PVLDB) 6(6):457\u2013468","journal-title":"Proc VLDB Endow (PVLDB)"},{"issue":"4","key":"457_CR15","doi-asserted-by":"crossref","first-page":"997","DOI":"10.1109\/TKDE.2013.43","volume":"26","author":"J Gao","year":"2014","unstructured":"Gao J, Zhou J, Yu JX, Wang T (2014) Shortest path computing in relational dbmss. IEEE Trans Knowl Data Eng 26(4):997\u20131011","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"457_CR16","unstructured":"Goldberg, A.V., Werneck, R.F.F. (2005) Computing point-to-point shortest paths from external memory. In: Proceedings of workshop on algorithm engineering and experiments and workshop on analytic algorithmics and combinatorics (ALENEX\/ANALCO), pp 26\u201340"},{"key":"457_CR17","doi-asserted-by":"crossref","unstructured":"Greco S, Molinaro C, Pulice C (2016) Efficient maintenance of all-pairs shortest distances. In: Proceedings of international conference on scientific and statistical database management (SSDBM), pp 9:1\u20139:12","DOI":"10.1145\/2949689.2949713"},{"key":"457_CR18","doi-asserted-by":"crossref","unstructured":"Greco S, Molinaro C, Pulice C, Quintana X (2016) All-pairs shortest distances maintenance in relational dbmss. In: Proceedings of IEEE\/ACM international conference on advances in social networks analysis and mining (ASONAM), pp 215\u2013222","DOI":"10.1109\/ASONAM.2016.7752238"},{"key":"457_CR19","doi-asserted-by":"crossref","unstructured":"Greco S, Molinaro C, Pulice C, Quintana X (2017) Efficient maximum flow maintenance on dynamic networks. In: Proceedings of international conference on world wide web companion (WWW), pp 1383\u20131385","DOI":"10.1145\/3041021.3051152"},{"key":"457_CR20","doi-asserted-by":"crossref","unstructured":"Greco S, Molinaro C, Pulice C, Quintana X (2017) Incremental maximum flow computation on evolving networks. In: Proceedings of the symposium on applied computing (SAC), pp 1061\u20131067","DOI":"10.1145\/3019612.3019816"},{"key":"457_CR21","doi-asserted-by":"crossref","unstructured":"Gupta A, Mumick I.S, Subrahmanian V.S (1993) Maintaining views incrementally. In: Proceedings of international conference on management of data (SIGMOD), pp 157\u2013166","DOI":"10.1145\/170035.170066"},{"key":"457_CR22","doi-asserted-by":"crossref","unstructured":"Henzinger M, Krinninger S, Nanongkai D (2013) Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. In: Proceedings of IEEE symposium on foundations of computer science (FOCS), pp 538\u2013547","DOI":"10.1109\/FOCS.2013.64"},{"issue":"1","key":"457_CR23","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/0020-0190(88)90136-6","volume":"28","author":"GF Italiano","year":"1988","unstructured":"Italiano GF (1988) Finding paths and deleting edges in directed acyclic graphs. Inf Process Lett 28(1):5\u201311","journal-title":"Inf Process Lett"},{"key":"457_CR24","doi-asserted-by":"crossref","unstructured":"Jin R, Ruan N, Xiang Y, Lee V.E. (2012) A highway-centric labeling approach for answering distance queries on large sparse graphs. In: Proceedings of international conference on management of data (SIGMOD), pp 445\u2013456","DOI":"10.1145\/2213836.2213887"},{"key":"457_CR25","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1016\/j.artint.2016.06.008","volume":"239","author":"C Kang","year":"2016","unstructured":"Kang C, Kraus S, Molinaro C, Spezzano F, Subrahmanian VS (2016) Diffusion centrality: a paradigm to maximize spread in social networks. Artif Intell 239:70\u201396","journal-title":"Artif Intell"},{"key":"457_CR26","unstructured":"Kang C, Molinaro C, Kraus S, Shavitt Y, Subrahmanian V.S (2012) Diffusion centrality in social networks. In: Proceedings of international conference on advances in social networks analysis and mining (ASONAM), pp 558\u2013564"},{"issue":"1","key":"457_CR27","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1007\/s13278-014-0220-6","volume":"4","author":"SS Khopkar","year":"2014","unstructured":"Khopkar SS, Nagi R, Nikolaev AG, Bhembre V (2014) Efficient algorithms for incremental all pairs shortest paths, closeness and betweenness in social network analysis. Soc Netw Anal Min 4(1):220","journal-title":"Soc Netw Anal Min"},{"key":"457_CR28","doi-asserted-by":"crossref","unstructured":"King, V (1999) Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In: Proceedings of IEEE symposium on foundations of computer science (FOCS), pp 81\u201391","DOI":"10.1109\/SFFCS.1999.814580"},{"issue":"3","key":"457_CR29","doi-asserted-by":"crossref","first-page":"698","DOI":"10.1145\/1093382.1093384","volume":"30","author":"C Pang","year":"2005","unstructured":"Pang C, Dong G, Ramamohanarao K (2005) Incremental maintenance of shortest distance and transitive closure in first-order logic and SQL. ACM Trans Database Syst 30(3):698\u2013721","journal-title":"ACM Trans Database Syst"},{"key":"457_CR30","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1613\/jair.3509","volume":"43","author":"L Planken","year":"2012","unstructured":"Planken L, de Weerdt M, van der Krogt R (2012) Computing all-pairs shortest paths by leveraging low treewidth. J Artif Intell Res 43:353\u2013388","journal-title":"J Artif Intell Res"},{"issue":"3","key":"457_CR31","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1093\/bioinformatics\/btg415","volume":"20","author":"N Przulj","year":"2004","unstructured":"Przulj N, Wigle DA, Jurisica I (2004) Functional topology in a network of protein interactions. Bioinformatics 20(3):340\u2013348","journal-title":"Bioinformatics"},{"issue":"1","key":"457_CR32","doi-asserted-by":"crossref","first-page":"61","DOI":"10.14778\/2732219.2732225","volume":"7","author":"Z Qi","year":"2013","unstructured":"Qi Z, Xiao Y, Shao B, Wang H (2013) Toward a distance oracle for billion-node graphs. Proc VLDB Endow (PVLDB) 7(1):61\u201372","journal-title":"Proc VLDB Endow (PVLDB)"},{"key":"457_CR33","doi-asserted-by":"crossref","unstructured":"Qiao M, Cheng H, Chang L, Yu J.X (2012) Approximate shortest distance computing: A query-dependent local landmark scheme. In: Proceedings of IEEE international conference on data engineering (ICDE), pp 462\u2013473","DOI":"10.1109\/ICDE.2012.53"},{"issue":"7","key":"457_CR34","doi-asserted-by":"crossref","first-page":"1189","DOI":"10.1093\/bioinformatics\/bti116","volume":"21","author":"SA Rahman","year":"2005","unstructured":"Rahman SA, Advani P, Schunk R, Schrader R, Schomburg D (2005) Metabolic pathway analysis web service (pathway hunter tool at cubic). Bioinformatics 21(7):1189\u20131193","journal-title":"Bioinformatics"},{"issue":"3","key":"457_CR35","doi-asserted-by":"crossref","first-page":"670","DOI":"10.1137\/090776573","volume":"41","author":"L Roditty","year":"2012","unstructured":"Roditty L, Zwick U (2012) Dynamic approximate all-pairs shortest paths in undirected graphs. SIAM J Comput 41(3):670\u2013683","journal-title":"SIAM J Comput"},{"issue":"2","key":"457_CR36","doi-asserted-by":"crossref","first-page":"10:1","DOI":"10.1145\/2480759.2480762","volume":"14","author":"P Shakarian","year":"2013","unstructured":"Shakarian P, Broecheler M, Subrahmanian VS, Molinaro C (2013) Using generalized annotated programs to solve social network diffusion optimization problems. ACM Trans Comput Logic 14(2):10:1\u201310:40","journal-title":"ACM Trans Comput Logic"},{"key":"457_CR37","doi-asserted-by":"crossref","first-page":"45:1","DOI":"10.1145\/2530531","volume":"46","author":"C Sommer","year":"2014","unstructured":"Sommer C (2014) Shortest-path queries in static networks. ACM Comput Surv 46:45:1\u201345:31","journal-title":"ACM Comput Surv"},{"issue":"1","key":"457_CR38","doi-asserted-by":"crossref","first-page":"46:1","DOI":"10.1007\/s13278-015-0276-y","volume":"5","author":"A Tagarelli","year":"2015","unstructured":"Tagarelli A, Interdonato R (2015) Time-aware analysis and ranking of lurkers in social networks. Soc Netw Anal Min 5(1):46:1\u201346:23","journal-title":"Soc Netw Anal Min"},{"issue":"5","key":"457_CR39","doi-asserted-by":"crossref","first-page":"406","DOI":"10.14778\/2140436.2140438","volume":"5","author":"L Wu","year":"2012","unstructured":"Wu L, Xiao X, Deng D, Cong G, Zhu AD, Zhou S (2012) Shortest path and distance queries on road networks: an experimental evaluation. Proc VLDB Endow (PVLDB) 5(5):406\u2013417","journal-title":"Proc VLDB Endow (PVLDB)"},{"key":"457_CR40","doi-asserted-by":"crossref","unstructured":"Zhu A.D, Ma H, Xiao X, Luo S, Tang Y, Zhou S (2013) Shortest path and distance queries on road networks: towards bridging theory and practice. In: Proceedings of international conference on management of data (SIGMOD), pp 857\u2013868","DOI":"10.1145\/2463676.2465277"},{"key":"457_CR41","doi-asserted-by":"crossref","unstructured":"Zhu A.D, Xiao X, Wang S, Lin W (2013) Efficient single-source shortest path and distance queries on large graphs. In: Proceedings of ACM SIGKDD international conference on knowledge discovery and data mining (KDD), pp 998\u20131006","DOI":"10.1145\/2487575.2487665"}],"container-title":["Social Network Analysis and Mining"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s13278-017-0457-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-017-0457-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-017-0457-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,1]],"date-time":"2019-10-01T22:31:26Z","timestamp":1569969086000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s13278-017-0457-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,1]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["457"],"URL":"https:\/\/doi.org\/10.1007\/s13278-017-0457-y","relation":{},"ISSN":["1869-5450","1869-5469"],"issn-type":[{"value":"1869-5450","type":"print"},{"value":"1869-5469","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,1]]},"article-number":"36"}}