Search Our Scientific Publications & Authors

Algorithmica 2019 30;81(2):497-518. Epub 2018 Jul 30.

Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw, Warsaw, Poland.

We introduce the non-commutative subset convolution-a convolution of functions useful when working with determinant-based algorithms. In order to compute it efficiently, we take advantage of Clifford algebras, a generalization of quaternions used mainly in the quantum field theory. We apply this tool to speed up algorithms counting subgraphs parameterized by the treewidth of a graph. Read More

Algorithmica 2019 7;81(1):317-342. Epub 2018 May 7.

6CSAIL, Massachusetts Institute of Technology, Cambridge, USA.

Two mobile robots are initially placed at the same point on an infinite line. Each robot may move on the line in either direction not exceeding its maximal speed. The robots need to find a stationary target placed at an unknown location on the line. Read More

Algorithmica 2019 2;81(1):124-166. Epub 2018 Apr 2.

1University of Liverpool, Liverpool, UK.

The problem of pollution control has been mainly studied in the environmental economics literature where the methodology of game theory is applied for the pollution control. To the best of our knowledge this is the first time this problem is studied from the computational point of view. We introduce a new network model for pollution control and present two applications of this model. Read More

Algorithmica 2019 18;81(2):476-496. Epub 2018 Sep 18.

1Institut für Theoretische Informatik, Leibniz Universität Hannover, Appelstrasse 4, 30167 Hannover, Germany.

In the present paper, we introduce the backdoor set approach into the field of temporal logic for the global fragment of linear temporal logic. We study the parameterized complexity of the satisfiability problem parameterized by the size of the backdoor. We distinguish between backdoor detection and evaluation of backdoors into the fragments of Horn and Krom formulas. Read More

Algorithmica 2018 14;80(10):2909-2940. Epub 2017 Aug 14.

Institute of Information Systems 184/2, TU Wien, Favoritenstrasse 9-11, 1040 Vienna, Austria.

A secure set in a graph is defined as a set of vertices such that for any the majority of vertices in the neighborhood of belongs to . It is known that deciding whether a set is secure in a graph is -complete. However, it is still open how this result contributes to the actual complexity of deciding whether for a given graph and integer , a non-empty secure set for of size at most exists. Read More

Algorithmica 2018 31;80(11):3253-3269. Epub 2017 Oct 31.

1Department of Computer Science, TU Eindhoven, Eindhoven, The Netherlands.

We study the following problem: preprocess a set of objects into a data structure that allows us to efficiently report all pairs of objects from that intersect inside an axis-aligned query range . We present data structures of size and with query time time, where is the number of reported pairs, for two classes of objects in : axis-aligned rectangles and objects with small union complexity. For the 3-dimensional case where the objects and the query range are axis-aligned boxes in  , we present a data structure of size and query time . Read More

Algorithmica 2018 22;80(11):2993-3022. Epub 2017 Aug 22.

2Department of Data Science and Knowledge Engineering (DKE), Maastricht University, Maastricht, The Netherlands.

The hybridization number problem requires us to embed a set of binary rooted phylogenetic trees into a binary rooted phylogenetic network such that the number of nodes with indegree two is minimized. However, from a biological point of view accurately inferring the root location in a phylogenetic tree is notoriously difficult and poor root placement can artificially inflate the hybridization number. To this end we study a number of relaxed variants of this problem. Read More

Algorithmica 2017 26;78(2):660-680. Epub 2016 Aug 26.

ASAP Research Group, School of Computer Science, University of Nottingham, Jubilee Campus, Wollaton Road, Nottingham, NG8 1BB UK.

Real-world optimisation problems are often dynamic. Previously good solutions must be updated or replaced due to changes in objectives and constraints. It is often claimed that evolutionary algorithms are particularly suitable for dynamic optimisation because a large population can contain different solutions that may be useful in the future. Read More

Algorithmica 2014 Mar;68(4):835-858

Dept. of Computer Science University of California, Irvine Irvine, CA 92697-3435 USA, http://www.ics.uci.edu/~goodrich/

We study sorting algorithms based on randomized round-robin comparisons. Specifically, we study Spin-the-bottle sort, where comparisons are unrestricted, and Annealing sort, where comparisons are restricted to a distance bounded by a parameter. Both algorithms are simple, randomized, data-oblivious sorting algorithms, which are useful in privacy-preserving computations, but, as we show, Annealing sort is much more efficient. Read More

Algorithmica 2014 22;68(1):41-61. Epub 2012 Jun 22.

Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Magyar tudósok körútja 2, 1117 Budapest, Hungary.

We study a family of problems where the goal is to make a graph Eulerian, i.e., connected and with all the vertices having even degrees, by a minimum number of deletions. Read More