Extreme Witnesses and Their Applications

DOI10.1007/978-3-319-26626-8_33zbMath1400.68148OpenAlexW2408073233MaRDI 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 complexitystring matchingBoolean matrix productwitnessesBoolean vector convolutionlightest trianglesminimum and maximum witnesses

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Algorithms on strings (68W32)

Cites Work

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

This page was built for publication: Extreme Witnesses and Their Applications