{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T04:16:41Z","timestamp":1751516201552,"version":"3.41.0"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319774039"},{"type":"electronic","value":"9783319774046"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"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":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-77404-6_39","type":"book-chapter","created":{"date-parts":[[2018,3,12]],"date-time":"2018-03-12T10:03:11Z","timestamp":1520848991000},"page":"529-543","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Incremental Strong Connectivity and\u00a02-Connectivity in Directed Graphs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9706-7409","authenticated-orcid":false,"given":"Loukas","family":"Georgiadis","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9492-9894","authenticated-orcid":false,"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3888-7391","authenticated-orcid":false,"given":"Nikos","family":"Parotsidis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,3,13]]},"reference":[{"key":"39_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Vassilevska Williams, V.: Popular conjectures imply strong lower bounds for dynamic problems. In: FOCS, pp. 434\u2013443 (2014)","DOI":"10.1109\/FOCS.2014.53"},{"issue":"6","key":"39_CR2","doi-asserted-by":"publisher","first-page":"2117","DOI":"10.1137\/S0097539797317263","volume":"28","author":"S Alstrup","year":"1999","unstructured":"Alstrup, S., Harel, D., Lauridsen, P.W., Thorup, M.: Dominators in linear time. SIAM J. Comput. 28(6), 2117\u20132132 (1999)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"39_CR3","doi-asserted-by":"publisher","first-page":"1077","DOI":"10.1016\/j.jcss.2006.02.003","volume":"72","author":"J Aspnes","year":"2006","unstructured":"Aspnes, J., Chang, K., Yampolskiy, A.: Inoculation strategies for victims of viruses and the sum-of-squares partition problem. J. Comput. Syst. Sci. 72(6), 1077\u20131093 (2006)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"39_CR4","doi-asserted-by":"publisher","first-page":"1533","DOI":"10.1137\/070693217","volume":"38","author":"AL Buchsbaum","year":"2008","unstructured":"Buchsbaum, A.L., Georgiadis, L., Kaplan, H., Rogers, A., Tarjan, R.E., Westbrook, J.R.: Linear-time algorithms for dominators and other path-evaluation problems. SIAM J. Comput. 38(4), 1533\u20131573 (2008)","journal-title":"SIAM J. Comput."},{"key":"39_CR5","doi-asserted-by":"publisher","first-page":"247901","DOI":"10.1103\/PhysRevLett.91.247901","volume":"91","author":"R Cohen","year":"2003","unstructured":"Cohen, R., Havlin, S., Ben-Avraham, D.: Efficient immunization strategies for computer networks and populations. Phys. Rev. Lett. 91, 247901 (2003)","journal-title":"Phys. Rev. Lett."},{"key":"39_CR6","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge (2009)","edition":"3"},{"key":"39_CR7","doi-asserted-by":"crossref","unstructured":"Eppstein, D., Galil, Z., Italiano, G.F.: Dynamic graph algorithms. In: Algorithms and Theory of Computation Handbook, 2nd edn, vol. 1, pp. 9:1\u20139:28. CRC Press (2009)","DOI":"10.1201\/9781584888239-c9"},{"issue":"2","key":"39_CR8","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/S0020-0190(96)00202-5","volume":"61","author":"PG Franciosa","year":"1997","unstructured":"Franciosa, P.G., Gambosi, G., Nanni, U.: The incremental maintenance of a depth-first-search tree in directed acyclic graphs. Inf. Process. Lett. 61(2), 113\u2013120 (1997)","journal-title":"Inf. Process. Lett."},{"key":"39_CR9","unstructured":"Georgiadis, L., Hansen, T.D., Italiano, G.F., Krinninger, S., Parotsidis, N.: Decremental data structures for connectivity and dominators in directed graphs. In: ICALP, pp. 42:1\u201342:15 (2017)"},{"key":"39_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1007\/978-3-642-33090-2_43","volume-title":"Algorithms \u2013 ESA 2012","author":"L Georgiadis","year":"2012","unstructured":"Georgiadis, L., Italiano, G.F., Laura, L., Santaroni, F.: An experimental study of dynamic dominators. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 491\u2013502. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-33090-2_43"},{"key":"39_CR11","doi-asserted-by":"crossref","unstructured":"Georgiadis, L., Italiano, G.F., Parotsidis, N.: Incremental 2-edge-connectivity in directed graphs. In: ICALP, pp. 49:1\u201349:15 (2016)","DOI":"10.1145\/2968448"},{"key":"39_CR12","doi-asserted-by":"crossref","unstructured":"Georgiadis, L., Italiano, G.F., Parotsidis, N.: Strong connectivity in directed graphs under failures, with applications. In: SODA, pp. 1880\u20131899 (2017)","DOI":"10.1137\/1.9781611974782.123"},{"issue":"5","key":"39_CR13","doi-asserted-by":"publisher","first-page":"e36321","DOI":"10.1371\/journal.pone.0036321","volume":"7","author":"J Gunawardena","year":"2012","unstructured":"Gunawardena, J.: A linear framework for time-scale separation in nonlinear biochemical systems. PLoS ONE 7(5), e36321 (2012)","journal-title":"PLoS ONE"},{"key":"39_CR14","doi-asserted-by":"crossref","unstructured":"Henzinger, M., Krinninger, S., Nanongkai, D., Saranurak, T.: Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In: STOC, pp. 21\u201330 (2015)","DOI":"10.1145\/2746539.2746609"},{"issue":"2","key":"39_CR15","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"39_CR16","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"39_CR17","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.tcs.2011.11.011","volume":"447","author":"GF Italiano","year":"2012","unstructured":"Italiano, G.F., Laura, L., Santaroni, F.: Finding strong bridges and strong articulation points in linear time. Theor. Comput. Sci. 447, 74\u201384 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"39_CR18","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., Tardos, \u00c9.: Maximizing the spread of influence through a social network. In: KDD, pp. 137\u2013146 (2003)","DOI":"10.1145\/956750.956769"},{"key":"39_CR19","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/978-3-642-15883-4_8","volume-title":"Machine Learning and Knowledge Discovery in Databases","author":"CJ Kuhlman","year":"2010","unstructured":"Kuhlman, C.J., Anil Kumar, V.S., Marathe, M.V., Ravi, S.S., Rosenkrantz, D.J.: Finding critical nodes for inhibiting diffusion of complex contagions in social networks. In: Balc\u00e1zar, J.L., Bonchi, F., Gionis, A., Sebag, M. (eds.) ECML PKDD 2010. LNCS (LNAI), vol. 6322, pp. 111\u2013127. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-15883-4_8"},{"key":"39_CR20","doi-asserted-by":"crossref","unstructured":"Mihal\u00e1k, M., Uzna\u0144ski, P., Yordanov, P.: Prime factorization of the Kirchhoff polynomial: compact enumeration of arborescences. In: ANALCO, pp. 93\u2013105 (2016)","DOI":"10.1137\/1.9781611974324.10"},{"key":"39_CR21","doi-asserted-by":"crossref","unstructured":"Paudel, N., Georgiadis, L., Italiano, G.F.: Computing critical nodes in directed graphs. In: ALENEX, pp. 43\u201357 (2017)","DOI":"10.1137\/1.9781611974768.4"},{"key":"39_CR22","doi-asserted-by":"crossref","unstructured":"Ramalingam, G., Reps, T.: An incremental algorithm for maintaining the dominator tree of a reducible flowgraph. In: POPL, pp. 287\u2013296 (1994)","DOI":"10.1145\/174675.177905"},{"issue":"3","key":"39_CR23","doi-asserted-by":"publisher","first-page":"963","DOI":"10.1109\/TNET.2012.2215882","volume":"21","author":"Y Shen","year":"2013","unstructured":"Shen, Y., Nguyen, N.P., Xuan, Y., Thai, M.T.: On the discovery of critical links and nodes for assessing network vulnerability. IEEE\/ACM Trans. Netw. 21(3), 963\u2013973 (2013)","journal-title":"IEEE\/ACM Trans. Netw."},{"issue":"2","key":"39_CR24","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF00268499","volume":"6","author":"RE Tarjan","year":"1976","unstructured":"Tarjan, R.E.: Edge-disjoint spanning trees and depth-first search. Acta Informatica 6(2), 171\u201385 (1976)","journal-title":"Acta Informatica"},{"issue":"1","key":"39_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s40649-015-0010-y","volume":"2","author":"M Ventresca","year":"2015","unstructured":"Ventresca, M., Aleman, D.: Efficiently identifying critical nodes in large complex networks. Comput. Soc. Netw. 2(1), 1\u201316 (2015)","journal-title":"Comput. Soc. Netw."}],"container-title":["Lecture Notes in Computer Science","LATIN 2018: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-77404-6_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T18:29:53Z","timestamp":1751480993000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-77404-6_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319774039","9783319774046"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-77404-6_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"13 March 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Latin American Symposium on Theoretical Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Buenos Aires","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Argentina","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 April 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 April 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"latin2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/latin2018.dc.uba.ar\/#","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}