Malmö University Publications
Change search
Link to record
Permanent link

Direct link
Persson, Mia
Publications (10 of 19) Show all publications
Lingas, A. & Persson, M. (2023). (min, + ) Matrix and Vector Products for Inputs Decomposable into Few Monotone Subsequences. In: Weili Wu, Guangmo Tong (Ed.), Computing and Combinatorics: 29th International Conference, COCOON 2023, Hawaii, HI, USA, December 15–17, 2023, Proceedings, Part II. Paper presented at Computing and Combinatorics 29th International Conference, COCOON 2023, Hawaii, HI, USA, December 15–17, 2023 (pp. 55-68). Springer
Open this publication in new window or tab >>(min, + ) Matrix and Vector Products for Inputs Decomposable into Few Monotone Subsequences
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]

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.

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
Available from: 2024-01-08 Created: 2024-01-08 Last updated: 2024-01-08Bibliographically approved
Lingas, A., Persson, M. & Sledneu, D. (2022). An Output-Sensitive Algorithm for All-Pairs Shortest Paths in Directed Acyclic Graphs. In: CALDAM 2022: Algorithms and Discrete Applied Mathematic. Paper presented at Conference on Algorithms and Discrete Applied Mathematics 2022 (pp. 140-151). Springer
Open this publication in new window or tab >>An Output-Sensitive Algorithm for All-Pairs Shortest Paths in Directed Acyclic Graphs
2022 (English)In: CALDAM 2022: Algorithms and Discrete Applied Mathematic, Springer, 2022, p. 140-151Conference paper, Published paper (Refereed)
Abstract [en]

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.

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
Available from: 2022-08-03 Created: 2022-08-03 Last updated: 2022-08-03Bibliographically approved
Gasieniec, L., Jansson, J., Levcopoulos, C., Lingas, A. & Persson, M. (2021). Pushing the Online Boolean Matrix-vector Multiplication conjecture off-line and identifying its easy cases. Journal of computer and system sciences (Print), 118, 108-118
Open this publication in new window or tab >>Pushing the Online Boolean Matrix-vector Multiplication conjecture off-line and identifying its easy cases
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]

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.

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)
Available from: 2021-04-01 Created: 2021-04-01 Last updated: 2024-02-05Bibliographically approved
Lingas, A. & Persson, M. (2020). Computing the Boolean Product of Two n x n Boolean Matrices Using O(n(2)) Mechanical Operations. International Journal of Unconventional Computing, 15(3), 225-236
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
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]

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.

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 ()
Available from: 2020-08-04 Created: 2020-08-04 Last updated: 2021-12-17Bibliographically approved
Dereniowski, D., Lingas, A., Osula, D., Persson, M. & Zylinski, P. (2019). Clearing directed subgraphs by mobile agents Variations on covering with paths (ed.). Journal of computer and system sciences (Print), 102, 57-68
Open this publication in new window or tab >>Clearing directed subgraphs by mobile agents Variations on covering with paths
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]

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.

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)
Available from: 2020-02-27 Created: 2020-02-27 Last updated: 2023-09-01Bibliographically approved
Gąsieniec, L., Jansson, J., Levcopoulos, C., Lingas, A. & Persson, M. (2019). Pushing the Online Matrix-Vector Conjecture Off-Line and Identifying Its Easy Cases. In: Yijia Chen, Xiaotie Deng, Mei Lu (Ed.), Frontiers in Algorithmics: 13th International Workshop, FAW 2019, Sanya, China, April 29 – May 3, 2019, Proceedings. Paper presented at 13th International Workshop, FAW 2019, Sanya, China, April 29 – May 3, 2019 (pp. 156-169). Springer
Open this publication in new window or tab >>Pushing the Online Matrix-Vector Conjecture Off-Line and Identifying Its Easy Cases
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]

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.

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
Available from: 2023-12-19 Created: 2023-12-19 Last updated: 2023-12-28Bibliographically approved
Lingas, A. & Persson, M. (2018). Extreme Witnesses and Their Applications (ed.). Algorithmica, 80(12), 3943-3957
Open this publication in new window or tab >>Extreme Witnesses and Their Applications
2018 (English)In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 80, no 12, p. 3943-3957Article in journal (Refereed) Published
Abstract [en]

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.

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)
Available from: 2020-02-27 Created: 2020-02-27 Last updated: 2024-02-05Bibliographically approved
Lingas, A., Persson, M. & Sledneu, D. (2017). Bounds for Semi-disjoint Bilinear Forms in a Unit-Cost Computational Model (ed.). In: (Ed.), (Ed.), Theory and Applications of Models of Computation: . Paper presented at International Conference on Theory and Applications of Models of Computation, Bern, Switzerland (20-22 April, 2017) (pp. 411-423). : Springer
Open this publication in new window or tab >>Bounds for Semi-disjoint Bilinear Forms in a Unit-Cost Computational Model
2017 (English)In: Theory and Applications of Models of Computation, Springer, 2017, p. 411-423Conference paper, Published paper (Refereed)
Abstract [en]

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.

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)
Available from: 2020-02-29 Created: 2020-02-29 Last updated: 2024-02-05Bibliographically approved
Dereniowski, D., Lingas, A., Persson, M., Urbańska, D. & Żyliński, P. (2017). The Snow Team Problem. In: Ralf Klasing; Marc Zeitoun (Ed.), Fundamentals of Computation Theory: 21st International Symposium, FCT 2017, Bordeaux, France, September 11–13, 2017, Proceedings. Paper presented at 21st International Symposium, FCT 2017, Bordeaux, France, September 11–13, 2017 (pp. 190-203). Springer
Open this publication in new window or tab >>The Snow Team Problem
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]

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.

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
Available from: 2023-12-14 Created: 2023-12-14 Last updated: 2023-12-14Bibliographically approved
Lingas, A. & Persson, M. (2015). A Fast Parallel Algorithm for Minimum-Cost Small Integral Flows (ed.). Algorithmica, 72(2), 607-619
Open this publication in new window or tab >>A Fast Parallel Algorithm for Minimum-Cost Small Integral Flows
2015 (English)In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 72, no 2, p. 607-619Article in journal (Refereed)
Abstract [en]

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.

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)
Available from: 2020-02-27 Created: 2020-02-27 Last updated: 2024-02-06Bibliographically approved
Organisations

Search in DiVA

Show all publications