{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,1]],"date-time":"2024-06-01T00:57:11Z","timestamp":1717203431673},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2013,3,26]],"date-time":"2013-03-26T00:00:00Z","timestamp":1364256000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,12]]},"DOI":"10.1007\/s00453-013-9769-0","type":"journal-article","created":{"date-parts":[[2013,3,25]],"date-time":"2013-03-25T16:13:40Z","timestamp":1364228020000},"page":"595-647","source":"Crossref","is-referenced-by-count":4,"title":["On the Computational Complexity of Measuring Global Stability of Banking Networks"],"prefix":"10.1007","volume":"70","author":[{"given":"Piotr","family":"Berman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bhaskar","family":"DasGupta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lakshmi","family":"Kaligounder","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Karpinski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,3,26]]},"reference":[{"key":"9769_CR1","first-page":"367","volume-title":"Network-Based Strategies and Competencies","author":"F. Allen","year":"2009","unstructured":"Allen, F., Babus, A.: Networks in Finance. In: Kleindorfer, P., Wind, J. (eds.) Network-Based Strategies and Competencies, pp. 367\u2013382. Wharton School Publishing (2009)"},{"issue":"1","key":"9769_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1086\/262109","volume":"108","author":"F. Allen","year":"2000","unstructured":"Allen, F., Gale, D.: Financial contagion. J. Polit. Econ. 108(1), 1\u201333 (2000)","journal-title":"J. Polit. Econ."},{"key":"9769_CR3","doi-asserted-by":"crossref","unstructured":"Amini, H., Cont, R., Minca, A.: Resilience to contagion in financial networks (2011). arXiv:1112.5687v1","DOI":"10.2139\/ssrn.1865997"},{"key":"9769_CR4","first-page":"805","volume-title":"44th ACM Symposium on Theory of Computing","author":"B. Applebaum","year":"2012","unstructured":"Applebaum, B.: Pseudorandom generators with long stretch and low locality from random local one-way functions. In: 44th ACM Symposium on Theory of Computing, pp. 805\u2013816 (2012)"},{"key":"9769_CR5","unstructured":"Babus, A.: The formation of financial networks. Tinbergen Institute Discussion Paper No. 2006-093\/2; FEEM Working Paper No. 69.2007 (2007)"},{"key":"9769_CR6","first-page":"423","volume-title":"Financial Development, Integration and Stability","author":"A. Babus","year":"2006","unstructured":"Babus, A.: Contagion risk in financial networks. In: Liebscher, K. (ed.) Financial Development, Integration and Stability, pp. 423\u2013440 (2006)"},{"key":"9769_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0166-218X(84)90086-6","volume":"9","author":"R. Bar-Yehuda","year":"1984","unstructured":"Bar-Yehuda, R., Moran, S.: On approximation problems related to the independent set and vertex cover problems. Discrete Appl. Math. 9, 1\u201310 (1984)","journal-title":"Discrete Appl. Math."},{"key":"9769_CR8","unstructured":"Berman, P., Karpinski, M.: On some tighter inapproximability results, Further Improvements, Electronic Colloquium on Computational Complexity. Technical Report TR98-029, (1998)"},{"key":"9769_CR9","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1109\/FOCS.2011.38","volume-title":"52nd IEEE Annual Symposium on Foundations of Computer Science","author":"L. Blume","year":"2011","unstructured":"Blume, L., Easley, D., Kleinberg, J., Kleinberg, R., Tardos, E.: Which networks are least susceptible to cascading failures? In: 52nd IEEE Annual Symposium on Foundations of Computer Science, pp. 393\u2013402 (2011)"},{"key":"9769_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1993574.1993576","volume-title":"12th ACM conference on Electronic commerce","author":"L. Blume","year":"2011","unstructured":"Blume, L., Easley, D., Kleinberg, J., Kleinberg, R., Tardos, E.: Network formation in the presence of contagious risk. In: 12th ACM conference on Electronic commerce, pp. 1\u201310 (2011)"},{"key":"9769_CR11","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1007\/978-3-642-17572-5_48","volume-title":"6th International Conference on Internet and Network Economics","author":"A. Borodin","year":"2010","unstructured":"Borodin, A., Filmus, Y., Oren, J.: Threshold models for competitive influence in social networks. In: 6th International Conference on Internet and Network Economics, pp. 539\u2013550 (2010)"},{"key":"9769_CR12","first-page":"109","volume-title":"Financial Markets and Financial Crises","author":"C.W. Calomiris","year":"1991","unstructured":"Calomiris, C.W., Gorton, G.: The origins of banking panics: models, facts, and bank regulation. In: Hubbard, R.G. (ed.) Financial Markets and Financial Crises, pp. 109\u2013174. University of Chicago Press, Chicago (1991)"},{"key":"9769_CR13","unstructured":"Castiglionesi, F., Navarro, N.: Optimal fragile financial networks. Tilburg University Discussion Paper no. 2007-100, Tilburg, The Netherlands: Tilburg University (2007)"},{"key":"9769_CR14","first-page":"1029","volume-title":"19th Annual ACM-SIAM symposium on Discrete algorithms","author":"N. Chen","year":"2008","unstructured":"Chen, N.: On the approximability of influence in social networks. In: 19th Annual ACM-SIAM symposium on Discrete algorithms, pp. 1029\u20131037 (2008)"},{"key":"9769_CR15","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1145\/1557019.1557047","volume-title":"15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"W. Chen","year":"2009","unstructured":"Chen, W., Wang, Y., Yang, S.: Efficient influence maximization in social networks. In: 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 199\u2013208 (2009)"},{"key":"9769_CR16","doi-asserted-by":"crossref","unstructured":"Coelho, F.C., Cruz, O.G., Code\u00e7o, C.T.: Epigrass: a tool to study disease spread in complex networks. Source Code Biol. Med. 3(3) (2008)","DOI":"10.1186\/1751-0473-3-3"},{"key":"9769_CR17","volume-title":"Handbook of Systemic Risk","author":"R. Cont","year":"2012","unstructured":"Cont, R., Moussa, A., Santos, E.B.: Network structure and systemic risk in banking systems. In: Fouque, J.P., Langsam, J. (eds.) Handbook of Systemic Risk. Cambridge University Press, Cambridge (2012)"},{"key":"9769_CR18","volume-title":"3rd Financial Risks","author":"J. Corbo","year":"2010","unstructured":"Corbo, J., Demange, G.: Contagion in financial networks: a random graph model. In: 3rd Financial Risks. International Forum, Paris, France (2010)"},{"key":"9769_CR19","unstructured":"Dasgupta, B.: Capital accumulation in the presence of informal credit contracts: does the incentive mechanism work better than credit rationing under asymmetric information? Working papers 2004-32, University of Connecticut, Department of Economics (2004)"},{"key":"9769_CR20","unstructured":"DasGupta, B., Kaligounder, L.: Global stability of financial networks against contagion: measure, evaluation and implications (2012). arXiv:1208.3789v1"},{"key":"9769_CR21","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1086\/261155","volume":"91","author":"D.W. Diamond","year":"1983","unstructured":"Diamond, D.W., Dybvig, P.H.: Bank runs, deposit insurance and liquidity. J. Polit. Econ. 91, 401\u2013419 (1983)","journal-title":"J. Polit. Econ."},{"issue":"4","key":"9769_CR22","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1287\/moor.7.4.515","volume":"7","author":"G. Dobson","year":"1982","unstructured":"Dobson, G.: Worst-case analysis of greedy heuristics for integer programming with nonnegative data. Math. Oper. Res. 7(4), 515\u2013531 (1982)","journal-title":"Math. Oper. Res."},{"key":"9769_CR23","unstructured":"Eboli, M.: Systemic risk in financial network: a graph theoretical approach. Mimeo, Univ. di Chieti, Pescara (2004)"},{"key":"9769_CR24","doi-asserted-by":"crossref","first-page":"S19","DOI":"10.7883\/yoken.JJID.2005.S9","volume":"58","author":"S. Eubank","year":"2005","unstructured":"Eubank, S.: Network based models of infectious disease spread. Jpn. J. Infect. Dis. 58, S19\u2013S13 (2005)","journal-title":"Jpn. J. Infect. Dis."},{"key":"9769_CR25","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1038\/nature02541","volume":"429","author":"S. Eubank","year":"2004","unstructured":"Eubank, S., Guclu, H., Kumar, V.S.A., Marathe, M.V., Srinivasan, A., Toroczkai, Z., Wang, N.: Modeling disease outbreaks in realistic urban social networks. Nature 429, 180\u2013183 (2004)","journal-title":"Nature"},{"key":"9769_CR26","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of lnn for approximating set cover. J. ACM 45, 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"9769_CR27","doi-asserted-by":"crossref","first-page":"337","DOI":"10.2307\/1907327","volume":"1","author":"I. Fisher","year":"1933","unstructured":"Fisher, I.: The debt-deflation theory of great depressions. Econometrica 1, 337\u2013357 (1933)","journal-title":"Econometrica"},{"issue":"3","key":"9769_CR28","doi-asserted-by":"crossref","first-page":"611","DOI":"10.2307\/2601198","volume":"32","author":"X. Freixas","year":"2000","unstructured":"Freixas, X., Parigi, B.M., Rochet, J.-C.: Systemic risk, interbank relations, and liquidity provision by the central bank. J. Money Credit Bank. 32(3), 611\u2013638 (2000)","journal-title":"J. Money Credit Bank."},{"issue":"1","key":"9769_CR29","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1353\/mcb.2003.0004","volume":"35","author":"C.H. Furfine","year":"2003","unstructured":"Furfine, C.H.: Interbank exposures: quantifying the risk of contagion. J. Money Credit Bank. 35(1), 111\u2013128 (2003)","journal-title":"J. Money Credit Bank."},{"issue":"2120","key":"9769_CR30","doi-asserted-by":"crossref","first-page":"2401","DOI":"10.1098\/rspa.2009.0410","volume":"466","author":"P. Gai","year":"2010","unstructured":"Gai, P., Kapadia, S.: Contagion in financial networks. Proc. R. Soc. A 466(2120), 2401\u20132423 (2010)","journal-title":"Proc. R. Soc. A"},{"key":"9769_CR31","volume-title":"Speech given at the Marcus-Evans Conference on Stress-Testing","author":"A. Haldane","year":"2009","unstructured":"Haldane, A.: Why banks failed the stress test. In: Speech given at the Marcus-Evans Conference on Stress-Testing, February 9\u201310 (2009). Available at http:\/\/www.bankofengland.co.uk\/publications\/speeches\/2009\/speech374.pdf"},{"key":"9769_CR32","doi-asserted-by":"crossref","unstructured":"Iazzetta, C., Manna, M.: The topology of the interbank market developements in Italy since 1990, Bank of Italy. Temi di Discussione (Working Paper) No. 711 (2009)","DOI":"10.2139\/ssrn.1478472"},{"key":"9769_CR33","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1145\/956750.956769","volume-title":"9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"D. Kempe","year":"2003","unstructured":"Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137\u2013146 (2003)"},{"key":"9769_CR34","volume-title":"The General Theory of Employment, Interest, and Money","author":"J.M. Keynes","year":"1936","unstructured":"Keynes, J.M.: The General Theory of Employment, Interest, and Money. Harcourt, Brace and Company, New York (1936)"},{"issue":"1","key":"9769_CR35","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0020-0190(99)00031-9","volume":"70","author":"S. Khuller","year":"1999","unstructured":"Khuller, S., Moss, A., Naor, J.: The budgeted maximum coverage problem. Inf. Process. Lett. 70(1), 39\u201345 (1999)","journal-title":"Inf. Process. Lett."},{"key":"9769_CR36","volume-title":"The Network Challenge: Strategy, Profit and Risk in an Interlinked World","author":"P.R. Kleindorfer","year":"2009","unstructured":"Kleindorfer, P.R., Wind, Y., Gunther, R.E.: The Network Challenge: Strategy, Profit and Risk in an Interlinked World. Pearson Prentice Hall, New York (2009)"},{"issue":"3","key":"9769_CR37","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1137\/S0097539702416736","volume":"33","author":"G. Kortsarz","year":"2004","unstructured":"Kortsarz, G., Krauthgamer, R., Lee, J.R.: Hardness of approximating vertex-connectivity network design problems. SIAM J. Comput. 33(3), 704\u2013720 (2004)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"9769_CR38","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1006\/jeth.2000.2733","volume":"99","author":"R. Lagunoff","year":"2001","unstructured":"Lagunoff, R., Schreft, S.: A model of financial fragility. J. Econ. Theory 99(1\u20132), 220\u2013264 (2001)","journal-title":"J. Econ. Theory"},{"key":"9769_CR39","doi-asserted-by":"crossref","unstructured":"Liedorp, F.R., Medema, L., Koetter, M., Koning, R.H., van Lelyveld, I.: Peer monitoring or contagion? Interbank market exposure and bank risk. DNB working paper No. 248 (2010)","DOI":"10.2139\/ssrn.1947310"},{"key":"9769_CR40","volume-title":"Financial Crises: Institutions and Markets in a Fragile Environment","author":"H. Minsky","year":"1977","unstructured":"Minsky, H.: A theory of systemic fragility. In: Altman, E.I., Sametz, A.W. (eds.) Financial Crises: Institutions and Markets in a Fragile Environment. Wiley, New York (1977)"},{"key":"9769_CR41","doi-asserted-by":"crossref","unstructured":"Mistrulli, P.E.: Assessing fiancial contagion in the interbank market: maximum entropy versus observed interbank lending patterns. Bank of Italy Research (2007)","DOI":"10.2139\/ssrn.1022523"},{"key":"9769_CR42","doi-asserted-by":"crossref","first-page":"2033","DOI":"10.1016\/j.jedc.2007.01.014","volume":"31","author":"E. Nier","year":"2007","unstructured":"Nier, E., Yang, J., Yorulmazer, T., Alentorn, A.: Network models and financial stability. J. Econ. Dyn. Control 31, 2033\u20132060 (2007)","journal-title":"J. Econ. Dyn. Control"},{"issue":"3","key":"9769_CR43","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R. Raz","year":"1998","unstructured":"Raz, R.: A parallel repetition theorem. SIAM J. Comput. 27(3), 763\u2013803 (1998)","journal-title":"SIAM J. Comput."},{"key":"9769_CR44","volume-title":"Introduction to Percolation Theory","author":"D. Stauffer","year":"1994","unstructured":"Stauffer, D., Aharony, A.: Introduction to Percolation Theory, 2nd edn. CRC Press, Boca Raton (1994)","edition":"2"},{"issue":"4","key":"9769_CR45","doi-asserted-by":"crossref","first-page":"827","DOI":"10.1016\/j.euroecorev.2003.12.009","volume":"48","author":"C. Upper","year":"2004","unstructured":"Upper, C., Worms, A.: Estimating bilateral exposures in the German interbank market: is there a danger of contagion? Eur. Econ. Rev. 48(4), 827\u2013849 (2004)","journal-title":"Eur. Econ. Rev."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9769-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9769-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9769-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,7]],"date-time":"2024-05-07T23:22:43Z","timestamp":1715124163000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9769-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3,26]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,12]]}},"alternative-id":["9769"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9769-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3,26]]}}}