RKRastislav Královič
Rastislav Královič
*This is an algorithmically generated author record based on publicly available information.
Research Subjects
Rastislav Královič has a total of 79 co-authors. Here are the top co-authors by number of shared publications:
Richard Královič
21 shared publicationsStefan Dobrev
Slovak Academy of Sciences
16 shared publications- Dennis Komm
ETH Zurich, Zurich, Switzerland
11 shared publications Dana Pardubská
Comenius University in Bratislava
7 shared publicationsJuraj Hromkovič
6 shared publicationsNicola Santoro
5 shared publications
Latest Publications
- 24 May 2026
- Published by Springer Nature
- p. 253-271
Cow Path by Finite Agent: Time vs Pebbles
- 5 December 2025
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 382, 214-233
Busy agents on a line
- 5 December 2025
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 382, 214-233
Busy agents on a line
- Open Access
- 30 January 2022
- Published by Springer Nature in Algorithmica
- Vol. 84 (5) , 1357-1384
Randomized Online Computation with High Probability Guarantees
We study the relationship between the competitive ratio and the tail distribution of randomized online problems. To this end, we identify a broad class of online problems for which the existence of a randomized online algorithm with constant expected competitive ratio r implies the existence of a randomized online algorithm that has a competitive ratio of $$(1+\varepsilon )r$$ with high probability, measured with respect to the optimal profit or cost, respectively. The class of problems includes some of the well-studied online problems such as paging, k-server, and metrical task systems on finite metric spaces.- 30 January 2022
- Published by Springer Nature in Algorithmica
- Vol. 84 (5) , 1357-1384
Open AccessRandomized Online Computation with High Probability Guarantees
We study the relationship between the competitive ratio and the tail distribution of randomized online problems. To this end, we identify a broad class of online problems for which the existence of a randomized online algorithm with constant expected competitive ratio r implies the existence of a randomized online algorithm that has a competitive ratio of $$(1+\varepsilon )r$$ with high probability, measured with respect to the optimal profit or cost, respectively. The class of problems includes some of the well-studied online problems such as paging, k-server, and metrical task systems on finite metric spaces. - 6 August 2021
- Published by Springer Nature
- p. 155-166
Two-Way Non-uniform Finite Automata
- 1 December 2020
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 114, 126-136
Tight hierarchy of data-independent multi-head automata
- 1 December 2020
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 114, 126-136
Tight hierarchy of data-independent multi-head automata
- Open Access
- 8 September 2020
- Published by MDPI AG in Algorithms
- Vol. 13 (9) , 225
A Linear-Time Algorithm for the Isometric Reconciliation of Unrooted Trees
In the reconciliation problem, we are given two phylogenetic trees. A species tree represents the evolutionary history of a group of species, and a gene tree represents the history of a family of related genes within these species. A reconciliation maps nodes of the gene tree to the corresponding points of the species tree, and thus helps to interpret the gene family history. In this paper, we study the case when both trees are unrooted and their edge lengths are known exactly. The goal is to root them and to find a reconciliation that agrees with the edge lengths. We show a linear-time algorithm for finding the set of all possible root locations, which is a significant improvement compared to the previous algorithm.- 8 September 2020
- Published by MDPI AG in Algorithms
- Vol. 13 (9) , 225
Open AccessA Linear-Time Algorithm for the Isometric Reconciliation of Unrooted Trees
In the reconciliation problem, we are given two phylogenetic trees. A species tree represents the evolutionary history of a group of species, and a gene tree represents the history of a family of related genes within these species. A reconciliation maps nodes of the gene tree to the corresponding points of the species tree, and thus helps to interpret the gene family history. In this paper, we study the case when both trees are unrooted and their edge lengths are known exactly. The goal is to root them and to find a reconciliation that agrees with the edge lengths. We show a linear-time algorithm for finding the set of all possible root locations, which is a significant improvement compared to the previous algorithm. - 28 July 2020
- Published by Springer Nature
- p. 146-162
Exploration of Time-Varying Connected Graphs with Silent Agents
- 28 July 2020
- Published by Springer Nature
- p. 146-162
Exploration of Time-Varying Connected Graphs with Silent Agents
- 9 August 2018
- Published by Springer Nature
- p. 3-16
Determinism and Nondeterminism in Finite Automata with Advice
- 9 August 2018
- Published by Springer Nature
- p. 3-16
Determinism and Nondeterminism in Finite Automata with Advice
- 29 June 2018
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 29 (04) , 551-569
Online Graph Coloring Against a Randomized Adversary
- 29 June 2018
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 29 (04) , 551-569
Online Graph Coloring Against a Randomized Adversary