Extreme witnesses and their applications

DOI10.1007/978-3-319-26626-8_33MaRDI QIDQ3467863zbMATH OpenOpenAlexFDO

Authors 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

Boolean matrix productBoolean vector convolutionlightest trianglesminimum and maximum witnessesstring matchingtime complexitywitnesses

Mathematics Subject Classification ID

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

Recommendations

• Extreme witnesses and their applications
• On minimum witnesses for Boolean matrix multiplication
• Witnesses for Boolean matrix multiplication and for transitive closure
• On Problems Equivalent to (min,+)-Convolution
• scientific article; zbMATH DE number 1256679

Cites work

• A Comparative Study of Efficient Algorithms for Partitioning a Sequence into Monotone Subsequences
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• All-pairs bottleneck paths in vertex weighted graphs
• Approximating minimum cocolorings.
• Clustered Integer 3SUM via Additive Combinatorics
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• Faster algorithms for finding lowest common ancestors in directed acyclic graphs
• Faster multi-witnesses for Boolean matrix multiplication
• Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication
• Finding heaviest H-subgraphs in real weighted graphs, with applications
• Finding Witnesses by Peeling
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1256679 (Why is no real title available?)
• scientific article; zbMATH DE number 801745 (Why is no real title available?)
• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
• Multiplying matrices faster than coppersmith-winograd
• Necklaces, Convolutions, and X + Y
• On minimum witnesses for Boolean matrix multiplication
• Powers of tensors and fast matrix multiplication

Cited in

(2)

• Extreme witnesses and their applications
• Optimal indecomposable witnesses without extremality or the spanning property

This page was built for publication: Extreme witnesses and their applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3467863)