Extreme Witnesses and Their Applications

DOI10.1007/978-3-319-26626-8_33zbMath1400.68148MaRDI QIDQ3467863

Mia Persson, Andrzej Lingas

Publication date: 5 February 2016

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2043/27262

zbMATH Keywords

time complexity; string matching; Boolean matrix product; witnesses; Boolean vector convolution; lightest triangles; minimum and maximum witnesses

Mathematics Subject Classification ID

68R05: Combinatorics in computer science

68W32: Algorithms on strings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On minimum witnesses for Boolean matrix multiplication
• All-pairs bottleneck paths in vertex weighted graphs
• Faster multi-witnesses for Boolean matrix multiplication
• Approximating minimum cocolorings.
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• Faster algorithms for finding lowest common ancestors in directed acyclic graphs
• Finding heaviest H -subgraphs in real weighted graphs, with applications
• Clustered Integer 3SUM via Additive Combinatorics
• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
• Powers of tensors and fast matrix multiplication
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• Finding Witnesses by Peeling
• Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication
• Multiplying matrices faster than coppersmith-winograd
• A Comparative Study of Efficient Algorithms for Partitioning a Sequence into Monotone Subsequences
• Necklaces, Convolutions, and X + Y