Extreme Witnesses and Their Applications
(2018) In Algorithmica 80(12). p.39433957 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 kwitness problem or the largest kwitness problem, respectively. We also study the corresponding smallest and largest kwitness problems for Boolean matrix product. First, we present an O~ (n^{1.5}k^{0.5}) time algorithm for the smallest or largest kwitness problem for the Boolean convolution of two ndimensional 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 kwitness problem or the largest kwitness problem, respectively. We also study the corresponding smallest and largest kwitness problems for Boolean matrix product. First, we present an O~ (n^{1.5}k^{0.5}) time algorithm for the smallest or largest kwitness problem for the Boolean convolution of two ndimensional 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 kwitness problem for the Boolean matrix product of two n× n Boolean matrices. It yields fast algorithms for reporting k lightest (heaviest) triangles in a vertexweighted graph.
(Less)
 author
 Lingas, Andrzej ^{LU} and Persson, Mia ^{LU}
 organization
 publishing date
 20180806
 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
 01784617
 DOI
 10.1007/s0045301804928
 language
 English
 LU publication?
 yes
 id
 c57913bde7ee47198604a3abe67390ae
 date added to LUP
 20180912 09:03:36
 date last changed
 20190114 15:44:46
@article{c57913bde7ee47198604a3abe67390ae, 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 kwitness problem or the largest kwitness problem, respectively. We also study the corresponding smallest and largest kwitness 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 kwitness problem for the Boolean convolution of two ndimensional 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 kwitness problem for the Boolean matrix product of two n× n Boolean matrices. It yields fast algorithms for reporting k lightest (heaviest) triangles in a vertexweighted graph.</p>}, author = {Lingas, Andrzej and Persson, Mia}, issn = {01784617}, 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 = {39433957}, publisher = {Springer}, series = {Algorithmica}, title = {Extreme Witnesses and Their Applications}, url = {http://dx.doi.org/10.1007/s0045301804928}, volume = {80}, year = {2018}, }