{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:02:25Z","timestamp":1758268945944,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540705741"},{"type":"electronic","value":"9783540705758"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"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":[[2008]]},"DOI":"10.1007\/978-3-540-70575-8_10","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"108-120","source":"Crossref","is-referenced-by-count":9,"title":["A New Combinatorial Approach for Sparse Graph Problems"],"prefix":"10.1007","author":[{"given":"Guy E.","family":"Blelloch","sequence":"first","affiliation":[]},{"given":"Virginia","family":"Vassilevska","sequence":"additional","affiliation":[]},{"given":"Ryan","family":"Williams","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"10_CR1","volume-title":"The design and analysis of computer algorithms","author":"A.V. Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.: The design and analysis of computer algorithms. Addison-Wesley Longman Publishing Co., Boston (1974)"},{"key":"10_CR2","first-page":"1209","volume":"11","author":"V.L. Arlazarov","year":"1970","unstructured":"Arlazarov, V.L., Dinic, E.A., Kronrod, M.A., Faradzev, I.A.: On economical construction of the transitive closure of an oriented graph. Soviet Math. Dokl.\u00a011, 1209\u20131210 (1970)","journal-title":"Soviet Math. Dokl."},{"key":"10_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/11534273_28","volume-title":"Algorithms and Data Structures","author":"T.M. Chan","year":"2005","unstructured":"Chan, T.M.: All-pairs shortest paths with real weights in O(n\n                              3\/logn) time. In: Dehne, F., L\u00f3pez-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol.\u00a03608, pp. 318\u2013324. Springer, Heidelberg (2005)"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Chan, T.M.: All-pairs shortest paths for unweighted undirected graphs in o(mn) time. In: Proc. SODA, pp. 514\u2013523 (2006)","DOI":"10.1145\/1109557.1109614"},{"issue":"6","key":"10_CR5","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/BF01940880","volume":"15","author":"J. Cheriyan","year":"1996","unstructured":"Cheriyan, J., Mehlhorn, K.: Algorithms for dense graphs and networks on the random access computer. Algorithmica\u00a015(6), 521\u2013549 (1996)","journal-title":"Algorithmica"},{"issue":"3","key":"10_CR6","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symbolic Computation\u00a09(3), 251\u2013280 (1990)","journal-title":"J. Symbolic Computation"},{"issue":"1\u20132","key":"10_CR7","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.tcs.2007.02.053","volume":"380","author":"A. Czumaj","year":"2007","unstructured":"Czumaj, A., Kowaluk, M., Lingas, A.: Faster algorithms for finding lowest common ancestors in directed acyclic graphs. TCS\u00a0380(1\u20132), 37\u201346 (2007)","journal-title":"TCS"},{"key":"10_CR8","unstructured":"Czumaj, A., Lingas, A.: Finding a heaviest triangle is not harder than matrix multiplication. In: Proc. SODA, pp. 986\u2013994 (2007)"},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"Feder, T., Motwani, R.: Clique partitions, graph compression and speeding-up algorithms. In: Proc. STOC, pp. 123\u2013133 (1991)","DOI":"10.1145\/103418.103424"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"Fischer, M.J., Meyer, A.R.: Boolean matrix multiplication and transitive closure. In: Proc. FOCS, pp. 129\u2013131 (1971)","DOI":"10.1109\/SWAT.1971.4"},{"key":"10_CR11","first-page":"243","volume":"54","author":"Z. Galil","year":"1997","unstructured":"Galil, Z., Margalit, O.: All pairs shortest paths for graphs with small integer length edges. JCSS\u00a054, 243\u2013254 (1997)","journal-title":"JCSS"},{"key":"10_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/11523468_20","volume-title":"Automata, Languages and Programming","author":"M. Kowaluk","year":"2005","unstructured":"Kowaluk, M., Lingas, A.: LCA Queries in Directed Acyclic Graphs. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 241\u2013248. Springer, Heidelberg (2005)"},{"issue":"2","key":"10_CR13","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/0020-0190(71)90006-8","volume":"1","author":"J.I. Munro","year":"1971","unstructured":"Munro, J.I.: Efficient determination of the transitive closure of a directed graph. Inf. Process. Lett.\u00a01(2), 56\u201358 (1971)","journal-title":"Inf. Process. Lett."},{"issue":"1\u20133","key":"10_CR14","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/S0019-9958(85)80024-3","volume":"67","author":"W. Rytter","year":"1985","unstructured":"Rytter, W.: Fast recognition of pushdown automaton and context-free languages. Information and Control\u00a067(1\u20133), 12\u201322 (1985)","journal-title":"Information and Control"},{"key":"10_CR15","first-page":"400","volume":"51","author":"R. Seidel","year":"1995","unstructured":"Seidel, R.: On the all-pairs-shortest-path problem in unweighted undirected graphs. JCSS\u00a051, 400\u2013403 (1995)","journal-title":"JCSS"},{"key":"10_CR16","unstructured":"Shapira, A., Yuster, R., Zwick, U.: All-pairs bottleneck paths in vertex weighted graphs. In: Proc. SODA, pp. 978\u2013985 (2007)"},{"key":"10_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/11786986_24","volume-title":"Automata, Languages and Programming","author":"V. Vassilevska","year":"2006","unstructured":"Vassilevska, V., Williams, R., Yuster, R.: Finding the Smallest  H-Subgraph in Real Weighted Graphs and Related Problems. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 262\u2013273. Springer, Heidelberg (2006)"},{"key":"10_CR18","unstructured":"Williams, R.: Matrix-vector multiplication in sub-quadratic time (some preprocessing required). In: Proc. SODA, pp. 995\u20131001 (2007)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70575-8_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T03:23:58Z","timestamp":1714620238000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-70575-8_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540705741","9783540705758"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70575-8_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}