Please wait ... |

Link to record
http://mau.diva-portal.org/smash/person.jsf?pid=authority-person:76988 $(function(){PrimeFaces.cw("InputTextarea","widget_formSmash_upper_j_idt142_recordDirectLink",{id:"formSmash:upper:j_idt142:recordDirectLink",widgetVar:"widget_formSmash_upper_j_idt142_recordDirectLink",autoResize:true});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt142_j_idt144",{id:"formSmash:upper:j_idt142:j_idt144",widgetVar:"widget_formSmash_upper_j_idt142_j_idt144",target:"formSmash:upper:j_idt142:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Permanent link

Direct link

Persson, Mia

Open this publication in new window or tab >>(min, + ) Matrix and Vector Products for Inputs Decomposable into Few Monotone Subsequences### Lingas, Andrzej

### Persson, Mia

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_0_j_idt208_some",{id:"formSmash:j_idt204:0:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_0_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_0_j_idt208_otherAuthors",{id:"formSmash:j_idt204:0:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_0_j_idt208_otherAuthors",multiple:true}); 2023 (English)In: Computing and Combinatorics: 29th International Conference, COCOON 2023, Hawaii, HI, USA, December 15–17, 2023, Proceedings, Part II / [ed] Weili Wu, Guangmo Tong, Springer, 2023, p. 55-68Conference paper, Published paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Springer, 2023
##### Series

Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 14423
##### National Category

Computer Sciences
##### Identifiers

urn:nbn:se:mau:diva-64866 (URN)10.1007/978-3-031-49193-1_5 (DOI)2-s2.0-85180531292 (Scopus ID)978-3-031-49192-4 (ISBN)978-3-031-49193-1 (ISBN)
##### Conference

Computing and Combinatorics 29th International Conference, COCOON 2023, Hawaii, HI, USA, December 15–17, 2023
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_0_j_idt208_j_idt379",{id:"formSmash:j_idt204:0:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_0_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_0_j_idt208_j_idt385",{id:"formSmash:j_idt204:0:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_0_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_0_j_idt208_j_idt391",{id:"formSmash:j_idt204:0:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_0_j_idt208_j_idt391",multiple:true});
#####

Available from: 2024-01-08 Created: 2024-01-08 Last updated: 2024-01-08Bibliographically approved

Department of Computer Science, Lund University, 22100, Lund, Sweden.

Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).

We study the time complexity of computing the (min, + ) matrix product of two n× n integer matrices in terms of n and the number of monotone subsequences the rows of the first matrix and the columns of the second matrix can be decomposed into. In particular, we show that if each row of the first matrix can be decomposed into at most m1 monotone subsequences and each column of the second matrix can be decomposed into at most m2 monotone subsequences such that all the subsequences are non-decreasing or all of them are non-increasing then the (min, + ) product of the matrices can be computed in O(m1m2n2.569) time. On the other hand, we observe that if all the rows of the first matrix are non-decreasing and all columns of the second matrix are non-increasing or vice versa then this case is as hard as the general one. Similarly, we also study the time complexity of computing the (min, + ) convolution of two n-dimensional integer vectors in terms of n and the number of monotone subsequences the two vectors can be decomposed into. We show that if the first vector can be decomposed into at most m1 monotone subsequences and the second vector can be decomposed into at most m2 subsequences such that all the subsequences of the first vector are non-decreasing and all the subsequences of the second vector are non-increasing or vice versa then their (min, + ) convolution can be computed in O~ (m1m2n1.5) time. On the other, the case when both vectors are non-decreasing or both of them are non-increasing is as hard as the general case.

Open this publication in new window or tab >>An Output-Sensitive Algorithm for All-Pairs Shortest Paths in Directed Acyclic Graphs### Lingas, Andrzej

### Persson, Mia

### Sledneu, Dzmitry

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_1_j_idt208_some",{id:"formSmash:j_idt204:1:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_1_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_1_j_idt208_otherAuthors",{id:"formSmash:j_idt204:1:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_1_j_idt208_otherAuthors",multiple:true}); 2022 (English)In: CALDAM 2022: Algorithms and Discrete Applied Mathematic, Springer, 2022, p. 140-151Conference paper, Published paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Springer, 2022
##### Series

Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 13179
##### Keywords

Directed graphs, Forestry, Graphic methods, Trees (mathematics), All pairs shortest paths, Directed paths, Integer parameters, Output-sensitive algorithm, Parameter T, Positive integers, Real edge weights, Shortest path problem, Single source shortest path problems, Weighted directed graph, Parameter estimation
##### National Category

Mathematics
##### Identifiers

urn:nbn:se:mau:diva-54295 (URN)10.1007/978-3-030-95018-7_12 (DOI)2-s2.0-85124662790 (Scopus ID)978-3-030-95017-0 (ISBN)978-3-030-95018-7 (ISBN)
##### Conference

Conference on Algorithms and Discrete Applied Mathematics 2022
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_1_j_idt208_j_idt379",{id:"formSmash:j_idt204:1:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_1_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_1_j_idt208_j_idt385",{id:"formSmash:j_idt204:1:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_1_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_1_j_idt208_j_idt391",{id:"formSmash:j_idt204:1:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_1_j_idt208_j_idt391",multiple:true});
#####

Available from: 2022-08-03 Created: 2022-08-03 Last updated: 2022-08-03Bibliographically approved

Department of Computer Science, Lund University, 22100, Lund, Sweden.

Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).

First, we present a new algorithm for the single-source shortest paths problem (SSSP) in edge-weighted directed graphs, with n vertices, m edges, and both positive and negative real edge weights. Given a positive integer parameter t, in O(tm) time the algorithm finds for each vertex v a path distance from the source to v not exceeding that yielded by the shortest path from the source to v among the so called t+ light paths. A directed path between two vertices is t+ light if it contains at most t more edges than the minimum edge-cardinality directed path between these vertices. For t= O(n), our algorithm yields an O(nm)-time solution to SSSP in directed graphs with real edge weights matching that of Bellman and Ford. Our main contribution is a new, output-sensitive algorithm for the all-pairs shortest paths problem (APSP) in directed acyclic graphs (DAGs) with positive and negative real edge weights. The running time of the algorithm depends on such parameters as the number of leaves in (lexicographically first) shortest-paths trees, and the in-degrees in the input graph. If the trees are sufficiently thin on the average, the algorithm is substantially faster than the best known algorithm. Finally, we discuss an extension of hypothetical improved upper time-bounds for APSP in non-negatively edge-weighted DAGs to include directed graphs with a polynomial number of large directed cycles. © 2022, Springer Nature Switzerland AG.

Open this publication in new window or tab >>Pushing the Online Boolean Matrix-vector Multiplication conjecture off-line and identifying its easy cases### Gasieniec, Leszek

### Jansson, Jesper

### Levcopoulos, Christos

### Lingas, Andrzej

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_2_j_idt208_some",{id:"formSmash:j_idt204:2:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_some",multiple:true}); ### Persson, Mia

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_2_j_idt208_otherAuthors",{id:"formSmash:j_idt204:2:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_otherAuthors",multiple:true}); Show others...PrimeFaces.cw("SelectBooleanButton","widget_formSmash_j_idt204_2_j_idt208_j_idt222",{id:"formSmash:j_idt204:2:j_idt208:j_idt222",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_j_idt222",onLabel:"Hide others...",offLabel:"Show others..."}); 2021 (English)In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 118, p. 108-118Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

Elsevier, 2021
##### Keywords

Boolean matrix, Product of matrix and vector, Dynamic graph problems, Online computation, Time complexity
##### National Category

Computer Sciences
##### Identifiers

urn:nbn:se:mau:diva-41520 (URN)10.1016/j.jcss.2020.12.004 (DOI)000615930900005 ()2-s2.0-85099348676 (Scopus ID)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_2_j_idt208_j_idt379",{id:"formSmash:j_idt204:2:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_2_j_idt208_j_idt385",{id:"formSmash:j_idt204:2:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_2_j_idt208_j_idt391",{id:"formSmash:j_idt204:2:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_j_idt391",multiple:true});
#####

Available from: 2021-04-01 Created: 2021-04-01 Last updated: 2024-02-05Bibliographically approved

University of Liverpool, England.

Hong Kong Polytech University, Peoples Republic of China.

Lund University.

Lund University.

Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).

Henzinger et al. posed the so-called Online Boolean Matrix-vector Multiplication (OMv) conjecture and showed that it implies tight hardness results for several basic dynamic or partially dynamic problems [STOC'15]. We first show that the OMv conjecture is implied by a simple off-line conjecture that we call the MvP conjecture. We then show that if the definition of the OMv conjecture is generalized to allow individual (i.e., it might be different for different matrices) polynomial-time preprocessing of the input matrix, then we obtain another conjecture (called the OMvP conjecture) that is in fact equivalent to our MvP conjecture. On the other hand, we demonstrate that the OMv conjecture does not hold in restricted cases where the rows of the matrix or the input vectors are clustered, and develop new efficient randomized algorithms for such cases. Finally, we present applications of our algorithms to answering graph queries. (c) 2021 Elsevier Inc. All rights reserved.

Open this publication in new window or tab >>Computing the Boolean Product of Two n x n Boolean Matrices Using O(n(2)) Mechanical Operations### Lingas, Andrzej

### Persson, Mia

Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_3_j_idt208_some",{id:"formSmash:j_idt204:3:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_3_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_3_j_idt208_otherAuthors",{id:"formSmash:j_idt204:3:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_3_j_idt208_otherAuthors",multiple:true}); 2020 (English)In: International Journal of Unconventional Computing, ISSN 1548-7199, E-ISSN 1548-7202, Vol. 15, no 3, p. 225-236Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

OLD CITY PUBLISHING INC, 2020
##### Keywords

Boolean matrix multiplication, Boolean matrix-vector multiplication, mechanical computing, time complexity
##### National Category

Computer Sciences
##### Identifiers

urn:nbn:se:mau:diva-17877 (URN)000540896600006 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_3_j_idt208_j_idt379",{id:"formSmash:j_idt204:3:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_3_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_3_j_idt208_j_idt385",{id:"formSmash:j_idt204:3:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_3_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_3_j_idt208_j_idt391",{id:"formSmash:j_idt204:3:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_3_j_idt208_j_idt391",multiple:true});
#####

Available from: 2020-08-04 Created: 2020-08-04 Last updated: 2021-12-17Bibliographically approved

Lund Univ, Dept Comp Sci, Lund, Sweden..

We study the problem of determining the Boolean product of two n x n Boolean matrices in an unconventional computational model allowing for mechanical operations. We show that O(n(2)) operations are sufficient to compute the product in this model.

Open this publication in new window or tab >>Clearing directed subgraphs by mobile agents Variations on covering with paths### Dereniowski, Dariusz

### Lingas, Andrzej

### Osula, Dorota

### Persson, Mia

Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_4_j_idt208_some",{id:"formSmash:j_idt204:4:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_some",multiple:true}); ### Zylinski, Pawel

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_4_j_idt208_otherAuthors",{id:"formSmash:j_idt204:4:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_otherAuthors",multiple:true}); Show others...PrimeFaces.cw("SelectBooleanButton","widget_formSmash_j_idt204_4_j_idt208_j_idt222",{id:"formSmash:j_idt204:4:j_idt208:j_idt222",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_j_idt222",onLabel:"Hide others...",offLabel:"Show others..."}); 2019 (English)In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 102, p. 57-68Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

Elsevier, 2019
##### Keywords

Covering with paths, FPT-algorithm, NP-hardness, Monomial
##### National Category

Computer Sciences
##### Identifiers

urn:nbn:se:mau:diva-2464 (URN)10.1016/j.jcss.2018.11.002 (DOI)000460197100005 ()2-s2.0-85057120191 (Scopus ID)30115 (Local ID)30115 (Archive number)30115 (OAI)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_4_j_idt208_j_idt379",{id:"formSmash:j_idt204:4:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_4_j_idt208_j_idt385",{id:"formSmash:j_idt204:4:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_4_j_idt208_j_idt391",{id:"formSmash:j_idt204:4:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_j_idt391",multiple:true});
#####

Available from: 2020-02-27 Created: 2020-02-27 Last updated: 2023-09-01Bibliographically approved

Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, 80-233 Gdańsk, Poland.

Department of Computer Science, Lund University, 221 00 Lund, Sweden.

Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, 80-233 Gdańsk, Poland.

Institute of Informatics, University of Gdańsk, 80-309 Gdańsk, Poland.

We study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initial positions may be pre-specified. In general, for a given subset S of vertices of a digraph D and a positive integer k, the objective is to determine whether there is a subgraph H = (V-H, A(H)) of D such that (a) S subset of V-H, (b) H is the union of k directed walks in D, and (c) the underlying graph of H includes a Steiner tree for S in D. Since a directed walk is a not necessarily a simple directed path, the problem is actually on covering with paths. We provide several results on the polynomial time tractability, hardness, and parameterized complexity of the problem. Our main fixed-parameter algorithm is randomized. (C) 2018 Elsevier Inc. All rights reserved.

Open this publication in new window or tab >>Pushing the Online Matrix-Vector Conjecture Off-Line and Identifying Its Easy Cases### Gąsieniec, Leszek

### Jansson, Jesper

### Levcopoulos, Christos

### Lingas, Andrzej

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_5_j_idt208_some",{id:"formSmash:j_idt204:5:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_some",multiple:true}); ### Persson, Mia

Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_5_j_idt208_otherAuthors",{id:"formSmash:j_idt204:5:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_otherAuthors",multiple:true}); Show others...PrimeFaces.cw("SelectBooleanButton","widget_formSmash_j_idt204_5_j_idt208_j_idt222",{id:"formSmash:j_idt204:5:j_idt208:j_idt222",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_j_idt222",onLabel:"Hide others...",offLabel:"Show others..."}); 2019 (English)In: Frontiers in Algorithmics: 13th International Workshop, FAW 2019, Sanya, China, April 29 – May 3, 2019, Proceedings / [ed] Yijia Chen, Xiaotie Deng, Mei Lu, Springer, 2019, p. 156-169Conference paper, Published paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Springer, 2019
##### Series

Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 11458
##### Keywords

Boolean matrix, Product of matrix and vector, Dynamic graph problems, Online computation, Time complexity
##### National Category

Computer Sciences
##### Identifiers

urn:nbn:se:mau:diva-64600 (URN)10.1007/978-3-030-18126-0_14 (DOI)2-s2.0-85065315076 (Scopus ID)978-3-030-18125-3 (ISBN)978-3-030-18126-0 (ISBN)
##### Conference

13th International Workshop, FAW 2019, Sanya, China, April 29 – May 3, 2019
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_5_j_idt208_j_idt379",{id:"formSmash:j_idt204:5:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_5_j_idt208_j_idt385",{id:"formSmash:j_idt204:5:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_5_j_idt208_j_idt391",{id:"formSmash:j_idt204:5:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_j_idt391",multiple:true});
#####

Available from: 2023-12-19 Created: 2023-12-19 Last updated: 2023-12-28Bibliographically approved

Department of Computer Science, University of Liverpool, Ashton Street, Liverpool, L69 38X, UK.

Department of Computing, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong.

Department of Computer Science, Lund University, 22100, Lund, Sweden.

Department of Computer Science, Lund University, 22100, Lund, Sweden.

Henzinger et al. posed the so called Online Boolean Matrix-vector Multiplication (OMv) conjecture and showed that it implies tight hardness results for several basic partially dynamic or dynamic problems [STOC’15].

We show that the OMv conjecture is implied by a simple off-line conjecture. If a not uniform (i.e., it might be different for different matrices) polynomial-time preprocessing of the matrix in the OMv conjecture is allowed then we can show such a variant of the OMv conjecture to be equivalent to our off-line conjecture. On the other hand, we show that the OMV conjecture does not hold in the restricted cases when the rows of the matrix or the input vectors are clustered.

Open this publication in new window or tab >>Extreme Witnesses and Their Applications### Lingas, Andrzej

### Persson, Mia

Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_6_j_idt208_some",{id:"formSmash:j_idt204:6:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_6_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_6_j_idt208_otherAuthors",{id:"formSmash:j_idt204:6:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_6_j_idt208_otherAuthors",multiple:true}); 2018 (English)In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 80, no 12, p. 3943-3957Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

Springer, 2018
##### Keywords

Boolean vector convolution, Boolean matrix product, String matching, Witnesses, Minimum and maximum witnesses, Lightest triangles, Time complexity
##### National Category

Engineering and Technology
##### Identifiers

urn:nbn:se:mau:diva-2631 (URN)10.1007/s00453-018-0492-8 (DOI)000447361100020 ()2-s2.0-85051750918 (Scopus ID)27262 (Local ID)27262 (Archive number)27262 (OAI)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_6_j_idt208_j_idt379",{id:"formSmash:j_idt204:6:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_6_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_6_j_idt208_j_idt385",{id:"formSmash:j_idt204:6:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_6_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_6_j_idt208_j_idt391",{id:"formSmash:j_idt204:6:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_6_j_idt208_j_idt391",multiple:true});
#####

Available from: 2020-02-27 Created: 2020-02-27 Last updated: 2024-02-05Bibliographically approved

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) over tilde (n(1.5)k(0.5))-time algorithm for the smallest or largest k-witness problem for the Boolean convolution of two n-dimensional vectors, where the notation (O) over tilde ( ) 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 x n Boolean matrices. It yields fast algorithms for reporting k lightest (heaviest) triangles in a vertex-weighted graph.

Open this publication in new window or tab >>Bounds for Semi-disjoint Bilinear Forms in a Unit-Cost Computational Model### Lingas, Andrzej

### Persson, Mia

### Sledneu, Dzmitry

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_7_j_idt208_some",{id:"formSmash:j_idt204:7:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_7_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_7_j_idt208_otherAuthors",{id:"formSmash:j_idt204:7:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_7_j_idt208_otherAuthors",multiple:true}); 2017 (English)In: Theory and Applications of Models of Computation, Springer, 2017, p. 411-423Conference paper, Published paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Springer, 2017
##### Series

Lecture Notes in Computer Science, ISSN 0302-9743 ; 10185
##### Keywords

Semi-disjoint bilinear form, Semi-ring, Vector convolution, Matrix multiplication, Distance product, Circuit complexity, Unit-cost ram, Time complexity
##### National Category

Engineering and Technology
##### Identifiers

urn:nbn:se:mau:diva-12397 (URN)10.1007/978-3-319-55911-7_30 (DOI)000425175500030 ()2-s2.0-85018441953 (Scopus ID)27328 (Local ID)27328 (Archive number)27328 (OAI)
##### Conference

International Conference on Theory and Applications of Models of Computation, Bern, Switzerland (20-22 April, 2017)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_7_j_idt208_j_idt379",{id:"formSmash:j_idt204:7:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_7_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_7_j_idt208_j_idt385",{id:"formSmash:j_idt204:7:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_7_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_7_j_idt208_j_idt391",{id:"formSmash:j_idt204:7:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_7_j_idt208_j_idt391",multiple:true});
#####

Available from: 2020-02-29 Created: 2020-02-29 Last updated: 2024-02-05Bibliographically approved

Malmö högskola, Faculty of Technology and Society (TS).

We study the complexity of the so called semi-disjoint bilinear forms over different semi-rings, in particular the n-dimensional vector convolution and n x n matrix product. We consider a powerful unit-cost computational model over the ring of integers allowing for several additional operations and generation of large integers. We show the following dichotomy for such a powerful model: while almost all arithmetic semi-disjoint bilinear forms have the same asymptotic time complexity as that yielded by naive algorithms, matrix multiplication, the so called distance matrix product, and vector convolution can be solved in a linear number of steps. It follows in particular that in order to obtain a non-trivial lower bounds for these three basic problems one has to assume restrictions on the set of allowed operations and/or the size of used integers.

Open this publication in new window or tab >>The Snow Team Problem### Dereniowski, Dariusz

### Lingas, Andrzej

### Persson, Mia

### Urbańska, Dorota

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_8_j_idt208_some",{id:"formSmash:j_idt204:8:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_some",multiple:true}); ### Żyliński, Paweł

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_8_j_idt208_otherAuthors",{id:"formSmash:j_idt204:8:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_otherAuthors",multiple:true}); Show others...PrimeFaces.cw("SelectBooleanButton","widget_formSmash_j_idt204_8_j_idt208_j_idt222",{id:"formSmash:j_idt204:8:j_idt208:j_idt222",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_j_idt222",onLabel:"Hide others...",offLabel:"Show others..."}); 2017 (English)In: Fundamentals of Computation Theory: 21st International Symposium, FCT 2017, Bordeaux, France, September 11–13, 2017, Proceedings / [ed] Ralf Klasing; Marc Zeitoun, Springer, 2017, p. 190-203Conference paper, Published paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Springer, 2017
##### Series

Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 10472
##### Keywords

Graph searching; FPT-algorithm; NP-hardness; Monomial
##### National Category

Computer Sciences
##### Identifiers

urn:nbn:se:mau:diva-64415 (URN)10.1007/978-3-662-55751-8_16 (DOI)000717257400016 ()2-s2.0-85029431842 (Scopus ID)978-3-662-55750-1 (ISBN)978-3-662-55751-8 (ISBN)
##### Conference

21st International Symposium, FCT 2017, Bordeaux, France, September 11–13, 2017
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_8_j_idt208_j_idt379",{id:"formSmash:j_idt204:8:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_8_j_idt208_j_idt385",{id:"formSmash:j_idt204:8:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_8_j_idt208_j_idt391",{id:"formSmash:j_idt204:8:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_j_idt391",multiple:true});
#####

Available from: 2023-12-14 Created: 2023-12-14 Last updated: 2023-12-14Bibliographically approved

Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, 80-233, Gdańsk, Poland.

Department of Computer Science, Lund University, 221 00, Lund, Sweden.

Malmö högskola, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).

Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, 80-233, Gdańsk, Poland.

Institute of Informatics, University of Gdańsk, 80-309, Gdańsk, Poland.

We study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initial positions may be pre-specified. In general, for a given subset � of vertices of a digraph D and a positive integer k, the objective is to determine whether there is a subgraph �=(��,��) of D such that (a) �⊆��, (b) H is the union of k directed walks in D, and (c) the underlying graph of H includes a Steiner tree for �. We provide several results on parameterized complexity and hardness of the problems.

Open this publication in new window or tab >>A Fast Parallel Algorithm for Minimum-Cost Small Integral Flows### Lingas, Andrzej

### Persson, Mia

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_9_j_idt208_some",{id:"formSmash:j_idt204:9:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_9_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_9_j_idt208_otherAuthors",{id:"formSmash:j_idt204:9:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_9_j_idt208_otherAuthors",multiple:true}); 2015 (English)In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 72, no 2, p. 607-619Article in journal (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Springer, 2015
##### Keywords

Maximum integral flow, Minimum-cost flow, Polynomial verification, Parallel algorithms, Randomized algorithms, Time complexity, Processor, complexity
##### National Category

Engineering and Technology
##### Identifiers

urn:nbn:se:mau:diva-2408 (URN)10.1007/s00453-013-9865-1 (DOI)000354066300011 ()2-s2.0-84929061709 (Scopus ID)20002 (Local ID)20002 (Archive number)20002 (OAI)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_9_j_idt208_j_idt379",{id:"formSmash:j_idt204:9:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_9_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_9_j_idt208_j_idt385",{id:"formSmash:j_idt204:9:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_9_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_9_j_idt208_j_idt391",{id:"formSmash:j_idt204:9:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_9_j_idt208_j_idt391",multiple:true});
#####

Available from: 2020-02-27 Created: 2020-02-27 Last updated: 2024-02-06Bibliographically approved

Malmö högskola, Faculty of Technology and Society (TS).

We present a new approach to the minimum-cost integral flow problem for small values of the flow. It reduces the problem to the tests of simple multivariate polynomials over a finite field of characteristic two for non-identity with zero. In effect, we show that a minimum-cost flow of value k in a network with n vertices, a sink and a source, integral edge capacities and positive integral edge costs polynomially bounded in n can be found by a randomized PRAM, with errors of exponentially small probability in n, running in O(klog(kn)+log(2)(kn)) time and using 2 (k) (kn) (O(1)) processors. Thus, in particular, for the minimum-cost flow of value O(logn), we obtain an RNC2 algorithm, improving upon time complexity of earlier NC and RNC algorithms.