Extreme witnesses and their applications
From MaRDI portal
Publication:1799232
DOI10.1007/s00453-018-0492-8zbMath1400.68149MaRDI QIDQ1799232
Publication date: 18 October 2018
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-018-0492-8
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
- Unnamed Item
- Necklaces, convolutions, and \(X+Y\)
- 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
- Finding a maximum weight triangle in n 3-Δ time, 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
- Finding, minimizing, and counting weighted subgraphs
- Multiplying matrices faster than coppersmith-winograd
- A Comparative Study of Efficient Algorithms for Partitioning a Sequence into Monotone Subsequences