Extreme witnesses and their applications

DOI10.1007/S00453-018-0492-8zbMATH Open1400.68149OpenAlexW2886764391WikidataQ129411504 ScholiaQ129411504MaRDI QIDQ1799232FDOQ1799232

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

Recommendations

• Extreme witnesses and their applications
• On minimum witnesses for Boolean matrix multiplication
• scientific article; zbMATH DE number 1256679
• Witnesses for Boolean matrix multiplication and for transitive closure
• Finding witnesses by peeling

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

• Title not available (Why is that?)
• Powers of tensors and fast matrix multiplication
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• Title not available (Why is that?)
• Title not available (Why is that?)
• Finding, minimizing, and counting weighted subgraphs
• Multiplying matrices faster than coppersmith-winograd
• Title not available (Why is that?)
• Clustered Integer 3SUM via Additive Combinatorics
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• Approximating minimum cocolorings.
• Faster algorithms for finding lowest common ancestors in directed acyclic graphs
• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
• Finding heaviest H -subgraphs in real weighted graphs, with applications
• Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication
• Necklaces, convolutions, and \(X+Y\)
• On minimum witnesses for Boolean matrix multiplication
• A Comparative Study of Efficient Algorithms for Partitioning a Sequence into Monotone Subsequences
• Finding a maximum weight triangle in n ^3-Δ time, with applications
• All-pairs bottleneck paths in vertex weighted graphs
• Faster multi-witnesses for Boolean matrix multiplication
• Finding Witnesses by Peeling

Cited In (3)

• Optimal indecomposable witnesses without extremality or the spanning property
• \((\min ,+)\) matrix and vector products for inputs decomposable into few monotone subsequences
• Finding Witnesses by Peeling

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 Q1799232)