Extreme Witnesses and Their Applications
(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)
- author
- Lingas, Andrzej LU and Persson, Mia LU
- organization
- publishing date
- 2018-08-06
- 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
- 2022-01-31 05:10:25
@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}},
keywords = {{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}},
doi = {{10.1007/s00453-018-0492-8}},
volume = {{80}},
year = {{2018}},
}