{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T11:14:18Z","timestamp":1770894858690,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540388753","type":"print"},{"value":"9783540388760","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11841036_27","type":"book-chapter","created":{"date-parts":[[2006,9,11]],"date-time":"2006-09-11T13:20:54Z","timestamp":1157980854000},"page":"280-291","source":"Crossref","is-referenced-by-count":32,"title":["Dynamic Programming and Fast Matrix Multiplication"],"prefix":"10.1007","author":[{"given":"Frederic","family":"Dorn","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"27_CR1","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00453-001-0116-5","volume":"33","author":"J. Alber","year":"2002","unstructured":"Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica\u00a033, 461\u2013493 (2002)","journal-title":"Algorithmica"},{"key":"27_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/3-540-45995-2_52","volume-title":"LATIN 2002: Theoretical Informatics","author":"J. Alber","year":"2002","unstructured":"Alber, J., Niedermeier, R.: Improved tree decomposition based algorithms for domination-like problems. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol.\u00a02286, pp. 613\u2013627. Springer, Heidelberg (2002)"},{"key":"27_CR3","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1006\/jcss.1997.1388","volume":"54","author":"N. Alon","year":"1997","unstructured":"Alon, N., Galil, Z., Margalit, O.: On the exponent of the all pairs shortest path problem. Journal of Computer and System Sciences\u00a054, 255\u2013262 (1997)","journal-title":"Journal of Computer and System Sciences"},{"key":"27_CR4","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/ijoc.15.3.233.16078","volume":"15","author":"W. Cook","year":"2003","unstructured":"Cook, W., Seymour, P.: Tour merging via branch-decomposition. INFORMS Journal on Computing\u00a015, 233\u2013248 (2003)","journal-title":"INFORMS Journal on Computing"},{"key":"27_CR5","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1006\/jcom.1997.0438","volume":"13","author":"D. Coppersmith","year":"1997","unstructured":"Coppersmith, D.: Rectangular matrix multiplication revisited. Journal of Complexity\u00a013, 42\u201349 (1997)","journal-title":"Journal of Complexity"},{"key":"27_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. Journal of Symbolic Computation\u00a09, 251\u2013280 (1990)","journal-title":"Journal of Symbolic Computation"},{"key":"27_CR7","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press and McGraw-Hill Book Company (2001)"},{"key":"27_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/11561071_11","volume-title":"Algorithms \u2013 ESA 2005","author":"F. Dorn","year":"2005","unstructured":"Dorn, F., Penninkx, E., Bodlaender, H., Fomin, F.V.: Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 95\u2013106. Springer, Heidelberg (2005)"},{"key":"27_CR9","doi-asserted-by":"crossref","unstructured":"Dorn, F., Penninkx, E., Bodlaender, H., Fomin, F.V.: Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions (manuscript, 2006), http:\/\/archive.cs.uu.nl\/pub\/RUU\/CS\/techreps\/CS-2006\/2006-006.pdf","DOI":"10.1007\/11561071_11"},{"key":"27_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1007\/11682462_37","volume-title":"LATIN 2006: Theoretical Informatics","author":"F. Dorn","year":"2006","unstructured":"Dorn, F., Telle, J.A.: Two birds with one stone: the best of branchwidth and treewidth with one algorithm. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol.\u00a03887, pp. 386\u2013397. Springer, Heidelberg (2006)"},{"key":"27_CR11","first-page":"168","volume-title":"SODA 2003: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"F.V. Fomin","year":"2003","unstructured":"Fomin, F.V., Thilikos, D.M.: Dominating sets in planar graphs: branch-width and exponential speed-up. In: SODA 2003: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, pp. 168\u2013177. ACM, New York (2003)"},{"key":"27_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1007\/978-3-540-27836-8_50","volume-title":"Automata, Languages and Programming","author":"F.V. Fomin","year":"2004","unstructured":"Fomin, F.V., Thilikos, D.M.: Fast parameterized algorithms for graphs on surfaces: Linear kernel and exponential speed-up. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 581\u2013592. Springer, Heidelberg (2004)"},{"key":"27_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1007\/978-3-540-24749-4_6","volume-title":"STACS 2004","author":"F.V. Fomin","year":"2004","unstructured":"Fomin, F.V., Thilikos, D.M.: A simple and fast approach for solving problems on planar graphs. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol.\u00a02996, pp. 56\u201367. Springer, Heidelberg (2004)"},{"key":"27_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/11523468_31","volume-title":"Automata, Languages and Programming","author":"Q.-P. Gu","year":"2005","unstructured":"Gu, Q.-P., Tamaki, H.: Optimal branch-decomposition of planar graphs in O(n 3) time. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 373\u2013384. Springer, Heidelberg (2005)"},{"key":"27_CR15","doi-asserted-by":"publisher","first-page":"900","DOI":"10.1137\/S0895480104445010","volume":"19","author":"P. Heggernes","year":"2005","unstructured":"Heggernes, P., Telle, J.A., Villanger, Y.: Computing minimal triangulations in time O(n \u03b1 log n)\u2009=\u2009o(n 2.376). SIAM Journal on Discrete Mathematics\u00a019, 900\u2013913 (2005)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"27_CR16","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0207033","volume":"7","author":"A. Itai","year":"1978","unstructured":"Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. SIAM Journal on Computing\u00a07, 413\u2013423 (1978)","journal-title":"SIAM Journal on Computing"},{"key":"27_CR17","first-page":"158","volume-title":"SODA 2003: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"D. Kratsch","year":"2003","unstructured":"Kratsch, D., Spinrad, J.: Between O(nm) and O(n \u03b1 ). In: SODA 2003: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, 2003, pp. 158\u2013167. ACM, New York (2003)"},{"key":"27_CR18","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1006\/jcss.1995.1078","volume":"51","author":"R. Seidel","year":"1995","unstructured":"Seidel, R.: On the all-pairs-shortest-path problem in unweighted undirected graphs. Journal of Computer and System Sciences\u00a051, 400\u2013403 (1995)","journal-title":"Journal of Computer and System Sciences"},{"key":"27_CR19","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"P.D. Seymour","year":"1994","unstructured":"Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica\u00a014, 217\u2013241 (1994)","journal-title":"Combinatorica"},{"key":"27_CR20","series-title":"Lecture Notes in Computer Science","first-page":"605","volume-title":"40th Annual Symposium on Foundations of Computer Science, (FOCS 1999)","author":"A. Shoshan","year":"1999","unstructured":"Shoshan, A., Zwick, U.: All pairs shortest paths in undirected graphs with integer weights. In: 40th Annual Symposium on Foundations of Computer Science (FOCS 1999). LNCS, pp. 605\u2013615. Springer, Heidelberg (1999)"},{"key":"27_CR21","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1137\/S0895480194275825","volume":"10","author":"J.A. Telle","year":"1997","unstructured":"Telle, J.A., Proskurowski, A.: Algorithms for vertex partitioning problems on partial k-trees. SIAM J. Discrete Math\u00a010, 529\u2013550 (1997)","journal-title":"SIAM J. Discrete Math"},{"key":"27_CR22","doi-asserted-by":"crossref","unstructured":"Vaidya, P.M.: Speeding-up linear programming using fast matrix multiplication. In: 30th Annual Symposium on Foundations of Computer Science (FOCS 1989), pp. 332\u2013337 (1989)","DOI":"10.1109\/SFCS.1989.63499"},{"key":"27_CR23","doi-asserted-by":"crossref","unstructured":"Vassilevska, V., Williams, R.: Finding a maximum weight triangle in n (3\u2009\u2212\u2009\u03b4) time, with applications. In: ACM Symposium on Theory of Computing (STOC 2006) (to appear, 2006), http:\/\/www.cs.cmu.edu\/~ryanw\/max-weight-triangle.pdf","DOI":"10.1145\/1132516.1132550"},{"key":"27_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1227","DOI":"10.1007\/978-3-540-27836-8_101","volume-title":"Automata, Languages and Programming","author":"R. Williams","year":"2004","unstructured":"Williams, R.: A new algorithm for optimal constraint satisfaction and its implications. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 1227\u20131237. Springer, Heidelberg (2004)"},{"key":"27_CR25","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1145\/567112.567114","volume":"49","author":"U. Zwick","year":"2002","unstructured":"Zwick, U.: All pairs shortest paths using bridging sets and rectangular matrix multiplication. Journal of the ACM\u00a049, 289\u2013317 (2002)","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11841036_27.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T20:33:13Z","timestamp":1736541193000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11841036_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540388753","9783540388760"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/11841036_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}