Extreme witnesses and their applications

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

Authors Andrzej Lingas, Mia Persson 

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 complexitystring matchingBoolean matrix productwitnessesBoolean vector convolutionlightest trianglesminimum and maximum witnesses

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
• scientific article; zbMATH DE number 1256679
• Witnesses for Boolean matrix multiplication and for transitive closure
• Finding witnesses by peeling

Cites Work

• Title not available (Why is no real title available?)
• scientific article; zbMATH DE number 3471577 (Why is no real title available?)
• 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?)
• 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 Witnesses by Peeling
• Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication
• Finding a maximum weight triangle in n ^3-Δ time, with applications
• Finding, minimizing, and counting weighted subgraphs
• 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 (4)

• Optimal indecomposable witnesses without extremality or the spanning property
• \((\min ,+)\) matrix and vector products for inputs decomposable into few monotone subsequences
• Extreme witnesses and their applications
• 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)