Advanced

Extreme Witnesses and Their Applications

Lingas, Andrzej LU and Persson, Mia LU (2018) In Algorithmica 80(12). p.3943-3957
Abstract

We study the problem of computing the so called minimum and maximum witnesses for Boolean vector convolution. We also consider a generalization of the problem which is to determine for each positive value at a coordinate of the convolution vector, q smallest (largest) witnesses, where q is the minimum of a parameter k and the number of witnesses for this coordinate. We term this problem the smallest k-witness problem or the largest k-witness problem, respectively. We also study the corresponding smallest and largest k-witness problems for Boolean matrix product. First, we present an O~ (n1.5k0.5) -time algorithm for the smallest or largest k-witness problem for the Boolean convolution of two n-dimensional vectors,... (More)

We study the problem of computing the so called minimum and maximum witnesses for Boolean vector convolution. We also consider a generalization of the problem which is to determine for each positive value at a coordinate of the convolution vector, q smallest (largest) witnesses, where q is the minimum of a parameter k and the number of witnesses for this coordinate. We term this problem the smallest k-witness problem or the largest k-witness problem, respectively. We also study the corresponding smallest and largest k-witness problems for Boolean matrix product. First, we present an O~ (n1.5k0.5) -time algorithm for the smallest or largest k-witness problem for the Boolean convolution of two n-dimensional vectors, where the notation O~() suppresses polylogarithmic in n factors. In consequence, we obtain new upper time bounds on reporting positions of mismatches in potential string alignments and on computing restricted cases of the (min , + ) vector convolution. Next, we present a fast (substantially subcubic in n and linear in k) algorithm for the smallest or largest k-witness problem for the Boolean matrix product of two n× n Boolean matrices. It yields fast algorithms for reporting k lightest (heaviest) triangles in a vertex-weighted graph.

(Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Boolean matrix product, Boolean vector convolution, Lightest triangles, Minimum and maximum witnesses, String matching, Time complexity, Witnesses
in
Algorithmica
volume
80
issue
12
pages
3943 - 3957
publisher
Springer
external identifiers
  • scopus:85051750918
ISSN
0178-4617
DOI
10.1007/s00453-018-0492-8
language
English
LU publication?
yes
id
c57913bd-e7ee-4719-8604-a3abe67390ae
date added to LUP
2018-09-12 09:03:36
date last changed
2019-01-14 15:44:46
@article{c57913bd-e7ee-4719-8604-a3abe67390ae,
  abstract     = {<p>We study the problem of computing the so called minimum and maximum witnesses for Boolean vector convolution. We also consider a generalization of the problem which is to determine for each positive value at a coordinate of the convolution vector, q smallest (largest) witnesses, where q is the minimum of a parameter k and the number of witnesses for this coordinate. We term this problem the smallest k-witness problem or the largest k-witness problem, respectively. We also study the corresponding smallest and largest k-witness problems for Boolean matrix product. First, we present an O~ (n<sup>1.5</sup>k<sup>0.5</sup>) -time algorithm for the smallest or largest k-witness problem for the Boolean convolution of two n-dimensional vectors, where the notation O~() suppresses polylogarithmic in n factors. In consequence, we obtain new upper time bounds on reporting positions of mismatches in potential string alignments and on computing restricted cases of the (min , + ) vector convolution. Next, we present a fast (substantially subcubic in n and linear in k) algorithm for the smallest or largest k-witness problem for the Boolean matrix product of two n× n Boolean matrices. It yields fast algorithms for reporting k lightest (heaviest) triangles in a vertex-weighted graph.</p>},
  author       = {Lingas, Andrzej and Persson, Mia},
  issn         = {0178-4617},
  keyword      = {Boolean matrix product,Boolean vector convolution,Lightest triangles,Minimum and maximum witnesses,String matching,Time complexity,Witnesses},
  language     = {eng},
  month        = {08},
  number       = {12},
  pages        = {3943--3957},
  publisher    = {Springer},
  series       = {Algorithmica},
  title        = {Extreme Witnesses and Their Applications},
  url          = {http://dx.doi.org/10.1007/s00453-018-0492-8},
  volume       = {80},
  year         = {2018},
}