Extreme Witnesses and Their Applications
From MaRDI portal
Publication:3467863
DOI10.1007/978-3-319-26626-8_33zbMath1400.68148MaRDI QIDQ3467863
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
time complexity; string matching; Boolean matrix product; witnesses; Boolean vector convolution; lightest triangles; minimum and maximum witnesses
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