Extreme witnesses and their applications

DOI10.1007/s00453-018-0492-8zbMath1400.68149MaRDI QIDQ1799232

Mia Persson, Andrzej Lingas

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

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
• 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