{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T10:42:50Z","timestamp":1742640170981,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2018,8,6]],"date-time":"2018-08-06T00:00:00Z","timestamp":1533513600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004359","name":"Swedish Research Council","doi-asserted-by":"crossref","award":["621-2011-6179"],"award-info":[{"award-number":["621-2011-6179"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,12]]},"DOI":"10.1007\/s00453-018-0492-8","type":"journal-article","created":{"date-parts":[[2018,8,6]],"date-time":"2018-08-06T12:03:06Z","timestamp":1533556986000},"page":"3943-3957","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Extreme Witnesses and Their Applications"],"prefix":"10.1007","volume":"80","author":[{"given":"Andrzej","family":"Lingas","sequence":"first","affiliation":[]},{"given":"Mia","family":"Persson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,8,6]]},"reference":[{"key":"492_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"AV Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.: The Design and Analysis of Computer Algorithms. Addison-Wesley Publishing Company, Reading (1974)"},{"key":"492_CR2","doi-asserted-by":"crossref","unstructured":"Alon, N., Galil, Z., Margalit, O., Naor, M.: Witnesses for Boolean matrix multiplication and for shortest paths. In: Proceedings of the 33rd Symposium on Foundations of Computer Science (FOCS), pp. 417\u2013426 (1992)","DOI":"10.1109\/SFCS.1992.267748"},{"key":"492_CR3","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1007\/BF01940874","volume":"16","author":"N Alon","year":"1996","unstructured":"Alon, N., Naor, M.: Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions. Algorithmica 16, 434\u2013449 (1996)","journal-title":"Algorithmica"},{"key":"492_CR4","doi-asserted-by":"crossref","unstructured":"Aumman, N., Levenstein, M., Levenstein, N., Tsur, D.: Finding witnesses by peeling. In: Proceedings of the Combinatorial Pattern Matching (CPM). LNCS, vol. 4580, pp. 28\u201339. Springer (2007)","DOI":"10.1007\/978-3-540-73437-6_6"},{"key":"492_CR5","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/s00453-012-9734-3","volume":"69","author":"D Bremner","year":"2014","unstructured":"Bremner, D., Chan, T.M., Demaine, E.D., Erickson, J., Hurtado, F., Iacono, J., Langerman, S., Patrascu, M., Taslakian, P.: Necklaces, convolutions and X + Y. Algorithmica 69, 294\u2013314 (2014)","journal-title":"Algorithmica"},{"key":"492_CR6","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Lewenstein, M.: Clustered integer 3SUM vis additive combinatorics. In: Proceedings of the 47th ACM Symposium on Theory of Computing (STOC 2015)","DOI":"10.1145\/2746539.2746568"},{"issue":"5","key":"492_CR7","doi-asserted-by":"publisher","first-page":"2025","DOI":"10.1137\/08071990X","volume":"39","author":"TM Chan","year":"2010","unstructured":"Chan, T.M.: More algorithms for all-pairs shortest paths in weighted graphs. SIAM J. Comput. 39(5), 2025\u20132089 (2010)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"492_CR8","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/s00453-012-9742-3","volume":"69","author":"K Cohen","year":"2014","unstructured":"Cohen, K., Yuster, R.: On minimum witnesses for Boolean matrix multiplication. Algorithmica 69(2), 431\u2013442 (2014)","journal-title":"Algorithmica"},{"key":"492_CR9","volume-title":"Text Algorithms","author":"M Crochemore","year":"1994","unstructured":"Crochemore, M., Rytter, W.: Text Algorithms. Oxford University Press, New York (1994)"},{"issue":"1-2","key":"492_CR10","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.tcs.2007.02.053","volume":"380","author":"Artur Czumaj","year":"2007","unstructured":"Czumaj, A., Kowaluk, M., Lingas, A.: Faster algorithms for finding lowest common ancestors in directed acyclic graphs. In the special ICALP 2005 issue of Theoretical Computer Science 380(1\u20132), 37\u201346 (2007)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"492_CR11","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/070695149","volume":"39","author":"A Czumaj","year":"2009","unstructured":"Czumaj, A., Lingas, A.: Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication. SIAM J. Comput. 39(2), 431\u2013444 (2009)","journal-title":"SIAM J. Comput."},{"key":"492_CR12","unstructured":"Fisher, M.J., Paterson, M.S.: String-matching and other products. In: Proceedings of the 7th SIAM-AMS Complexity of Computation, pp. 113\u2013125 (1974)"},{"key":"492_CR13","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/S0020-0190(02)00288-0","volume":"84","author":"FV Fomin","year":"2002","unstructured":"Fomin, F.V., Kratsch, D., Novelli, J.: Approximating minimum cocolorings. Inf. Process. Lett. 84, 285\u2013290 (2002)","journal-title":"Inf. Process. Lett."},{"key":"492_CR14","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1016\/j.ipl.2008.10.012","volume":"109","author":"L Gasieniec","year":"2009","unstructured":"Gasieniec, L., Kowaluk, M., Lingas, A.: Faster multi-witnesses for Boolean matrix product. Inf. Process. Lett. 109, 242\u2013247 (2009)","journal-title":"Inf. Process. Lett."},{"key":"492_CR15","doi-asserted-by":"crossref","unstructured":"Le Gall, F.: Powers of tensors and fast matrix multiplication. In: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pp. 296\u2013303 (2014)","DOI":"10.1145\/2608628.2608664"},{"key":"492_CR16","doi-asserted-by":"crossref","unstructured":"Le Gall, F.: Faster algorithms for rectangular matrix multiplication. In: Proceedings of the 53rd Symposium on Foundations of Computer Science (FOCS), pp. 514\u2013523 (2012)","DOI":"10.1109\/FOCS.2012.80"},{"key":"492_CR17","doi-asserted-by":"crossref","unstructured":"Muthukrshnan, S.: New results and open problems related to non-standard stringology. In: 6th Proceedings of the Combinatorial Pattern Matching (CPM). LNCS, vol. 937, pp. 298\u2013317. Springer (1995)","DOI":"10.1007\/3-540-60044-2_50"},{"key":"492_CR18","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1007\/s00453-009-9328-x","volume":"59","author":"A Shapira","year":"2011","unstructured":"Shapira, A., Yuster, R., Zwick, U.: All-pairs bottleneck paths in vertex weighted graphs. Algorithmica 59, 621\u2013633 (2011)","journal-title":"Algorithmica"},{"key":"492_CR19","doi-asserted-by":"crossref","unstructured":"Vassilevska, V., Williams, R.: Finding a maximum weight triangle in $n^{3 - \\delta }$ time, with applications. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC 2006), pp. 225\u2013231. ACM (2006)","DOI":"10.1145\/1132516.1132550"},{"key":"492_CR20","doi-asserted-by":"crossref","unstructured":"Vassilevska, V., Williams, R.: Finding, minimizing, and counting weighted subgraphs. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC 2009), pp. 455\u2013463. ACM (2009)","DOI":"10.1145\/1536414.1536477"},{"issue":"3","key":"492_CR21","doi-asserted-by":"publisher","first-page":"44:1","DOI":"10.1145\/1798596.1798597","volume":"6","author":"V Vassilevska","year":"2010","unstructured":"Vassilevska, V., Williams, R., Yuster, R.: Finding heaviest H-subgraphs in real weighted graphs, with applications. ACM Trans. Algorithms 6(3), 44:1\u201344:23 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"492_CR22","doi-asserted-by":"crossref","unstructured":"Vassilevska Williams, V.: Multiplying matrices faster than Coppersmith\u2013Winograd. In: Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), pp. 887\u2013898 (2012)","DOI":"10.1145\/2213977.2214056"},{"key":"492_CR23","doi-asserted-by":"crossref","unstructured":"Yang, B., Chen, J., Lu, E., Zheng, S.Q.: A Comparative study of efficient algorithms for partitioning a sequence into monotone subsequences. In: Proceedings of the 4th Theory and Applications of Models of Computation (TAMC). LNCS, vol. 4484, pp. 46\u201357. Springer (2007)","DOI":"10.1007\/978-3-540-72504-6_4"},{"issue":"3","key":"492_CR24","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. J. ACM 49(3), 289\u2013317 (2002)","journal-title":"J. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0492-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0492-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0492-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,5]],"date-time":"2019-08-05T19:04:28Z","timestamp":1565031868000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0492-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,6]]},"references-count":24,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["492"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0492-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,8,6]]},"assertion":[{"value":"20 April 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 July 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 August 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}