Extreme witnesses and their applications
type: Item
instance of: scholarly article
title: Extreme witnesses and their applications
zbMATH Open document ID: 1400.68149
author: Andrzej Lingas
author: Mia Persson
published in: Algorithmica
publication date: 2018-10-18T00:00:00Z
Mathematics Subject Classification ID: 68R05
Mathematics Subject Classification ID: 68W32
zbMATH DE Number: 6958256
zbMATH Keywords: Boolean vector convolution
zbMATH Keywords: Boolean matrix product
zbMATH Keywords: string matching
zbMATH Keywords: witnesses
zbMATH Keywords: minimum and maximum witnesses
zbMATH Keywords: lightest triangles
zbMATH Keywords: time complexity
MaRDI profile type: Publication
full work available at URL: s00453-018-0492-8
OpenAlex ID: W2886764391
cites work: Q4091421
cites work: Q4230366
cites work: Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
cites work: Finding Witnesses by Peeling
cites work: Necklaces, convolutions, and \(X+Y\)
cites work: Clustered Integer 3SUM via Additive Combinatorics
cites work: More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
cites work: On minimum witnesses for Boolean matrix multiplication
cites work: Q4849531
cites work: Faster algorithms for finding lowest common ancestors in directed acyclic graphs
cites work: Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication
cites work: Q4055156
cites work: Approximating minimum cocolorings.
cites work: Faster multi-witnesses for Boolean matrix multiplication
cites work: Powers of tensors and fast matrix multiplication
cites work: All-pairs bottleneck paths in vertex weighted graphs
cites work: Finding a maximum weight triangle in n 3-Δ time, with applications
cites work: Finding, minimizing, and counting weighted subgraphs
cites work: Finding heaviest H -subgraphs in real weighted graphs, with applications
cites work: Multiplying matrices faster than coppersmith-winograd
cites work: A Comparative Study of Efficient Algorithms for Partitioning a Sequence into Monotone Subsequences
cites work: All pairs shortest paths using bridging sets and rectangular matrix multiplication
Wikidata QID: Q129411504
DOI: 10.1007/S00453-018-0492-8
description: scientific article; zbMATH DE number 6958256