Rastislav Kralovic

Orcid: 0000-0003-1121-1009

According to our database1, Rastislav Kralovic authored at least 66 papers between 1997 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Tree Coloring: Random Order and Predictions.
CoRR, 2024

2023
Two-Way Non-Uniform Finite Automata.
Int. J. Found. Comput. Sci., 2023

2022
Randomized Online Computation with High Probability Guarantees.
Algorithmica, 2022

2020
Tight hierarchy of data-independent multi-head automata.
J. Comput. Syst. Sci., 2020

A Linear-Time Algorithm for the Isometric Reconciliation of Unrooted Trees.
Algorithms, 2020

Exploration of Time-Varying Connected Graphs with Silent Agents.
Proceedings of the Structural Information and Communication Complexity, 2020

Improved Lower Bounds for Shoreline Search.
Proceedings of the Structural Information and Communication Complexity, 2020

Randomization in Non-Uniform Finite Automata.
Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

2018
Online Graph Coloring Against a Randomized Adversary.
Int. J. Found. Comput. Sci., 2018

Determinism and Nondeterminism in Finite Automata with Advice.
Proceedings of the Adventures Between Lower Bounds and Higher Altitudes, 2018

2017
Improved analysis of the online set cover problem with advice.
Theor. Comput. Sci., 2017

On the advice complexity of the k-server problem.
J. Comput. Syst. Sci., 2017

On the Cost of Waking Up.
Int. J. Netw. Comput., 2017

Online algorithms with advice: The tape model.
Inf. Comput., 2017

Treasure Hunt with Barely Communicating Agents.
Proceedings of the 21st International Conference on Principles of Distributed Systems, 2017

2016
The Complexity of Paging Against a Probabilistic Adversary.
Proceedings of the SOFSEM 2016: Theory and Practice of Computer Science, 2016

Advice Complexity of the Online Induced Subgraph Problem.
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Edge-Editing to a Dense and a Sparse Graph Class.
Proceedings of the LATIN 2016: Theoretical Informatics, 2016

On the Complexity of Distributed Wake-Up.
Proceedings of the Fourth International Symposium on Computing and Networking, 2016

2015
Advice Complexity of Maximum Independent set in Sparse and Bipartite Graphs.
Theory Comput. Syst., 2015

Treasure Hunt with Advice.
Proceedings of the Structural Information and Communication Complexity, 2015

Disjoint Path Allocation with Sublinear Advice.
Proceedings of the Computing and Combinatorics - 21st International Conference, 2015

2014
Randomized Online Algorithms with High Probability Guarantees.
Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

Advice Complexity: Quantitative Approach to A-Priori Information - (Extended Abstract).
Proceedings of the SOFSEM 2014: Theory and Practice of Computer Science, 2014

2013
Exploring an unknown dangerous graph using tokens.
Theor. Comput. Sci., 2013

Efficient routing in carrier-based mobile networks.
Theor. Comput. Sci., 2013

Determinism vs. Nondeterminism for Two-Way Automata: Representing the Meaning of States by Logical Formulæ.
Int. J. Found. Comput. Sci., 2013

Computing with Advice: when Knowledge Helps.
Bull. EATCS, 2013

2012
Independent Set with Advice: The Impact of Graph Knowledge - (Extended Abstract).
Proceedings of the Approximation and Online Algorithms - 10th International Workshop, 2012

Online Graph Exploration with Advice.
Proceedings of the Structural Information and Communication Complexity, 2012

2011
Local 7-coloring for planar subgraphs of unit disk graphs.
Theor. Comput. Sci., 2011

Routing in Carrier-Based Mobile Networks.
Proceedings of the Structural Information and Communication Complexity, 2011

2010
Periodic Data Retrieval Problem in Rings Containing a Malicious Host.
Proceedings of the Structural Information and Communication Complexity, 2010

Information Complexity of Online Problems.
Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

2009
Rapid almost-complete broadcasting in faulty networks.
Theor. Comput. Sci., 2009

Measuring the problem-relevant information in input.
RAIRO Theor. Informatics Appl., 2009

Antibandwidth and Cyclic Antibandwidth of Hamming Graphs.
Electron. Notes Discret. Math., 2009

Black Hole Search in Directed Graphs.
Proceedings of the Structural Information and Communication Complexity, 2009

On the Advice Complexity of Online Problems.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

2008
On fractional dynamic faults with thresholds.
Theor. Comput. Sci., 2008

How Much Information about the Future Is Needed?
Proceedings of the SOFSEM 2008: Theory and Practice of Computer Science, 2008

Leader Election in Extremely Unreliable Rings and Complete Networks.
Proceedings of the Principles of Distributed Systems, 12th International Conference, 2008

Deterministic Models of Communication Faults.
Proceedings of the Mathematical Foundations of Computer Science 2008, 2008

2007
Ranks of graphs: The size of acyclic orientation cover for deadlock-free packet routing.
Theor. Comput. Sci., 2007

Preface.
Theor. Comput. Sci., 2007

Eliminating graphs by means of parallel knock-out schemes.
Discret. Appl. Math., 2007


2006
Black hole search in common interconnection networks.
Networks, 2006

On Fractional Dynamic Faults with Threshold.
Proceedings of the Structural Information and Communication Complexity, 2006

Exploring an Unknown Graph to Locate a Black Hole Using Tokens.
Proceedings of the Fourth IFIP International Conference on Theoretical Computer Science (TCS 2006), 2006

Black Hole Search in Asynchronous Rings Using Tokens.
Proceedings of the Algorithms and Complexity, 6th Italian Conference, 2006

2005
On Semi-perfect 1-Factorizations.
Proceedings of the Structural Information and Communication Complexity, 2005

2003
Sparse topologies with small spectrum size.
Theor. Comput. Sci., 2003

On time versus size for monotone dynamic monopolies in regular topologies.
J. Discrete Algorithms, 2003

Minimum feedback vertex sets in shuffle-based interconnection networks.
Inf. Process. Lett., 2003

Broadcasting with Many Faulty Links.
Proceedings of the SIROCCO 10: Proceedings of the 10th Internaltional Colloquium on Structural Information Complexity, 2003

2002
Efficient Deadlock-free Multidimensional Interval Routing in Hypercube-like Networks.
Comput. Artif. Intell., 2002

Black Hole Search by Mobile Agents in Hypercubes and Related Networks.
Proceedings of the Procedings of the 6th International Conference on Principles of Distributed Systems. OPODIS 2002, 2002

2001
Scalable Sparse Topologies with Small Spectrum.
Proceedings of the STACS 2001, 2001

On Majority Voting Games in Trees.
Proceedings of the SOFSEM 2001: Theory and Practice of Informatics, 28th Conference on Current Trends in Theory and Practice of Informatics Piestany, Slovak Republic, November 24, 2001

On Immunity and Catastrophic Indices of Graphs.
Proceedings of the SIROCCO 8, 2001

2000
The complexity of shortest path and dilation bounded interval routing.
Theor. Comput. Sci., 2000

1999
Rank of Graphs: The Size of Acyclic Orientation Cover for Deadlock-Free Packet Routing.
Proceedings of the SIROCCO'99, 1999

Interval Routing on Layered Cross Product of Trees and Cycles.
Proceedings of the Euro-Par '99 Parallel Processing, 5th International Euro-Par Conference, Toulouse, France, August 31, 1999

1998
Efficient Deadlock-Free Multi-dimensional Interval Routing in Interconnection Networks.
Proceedings of the Distributed Computing, 12th International Symposium, 1998

1997
Time Optimal Self-Stabilizing Algorithms.
Proceedings of the SOFSEM '97: Theory and Practice of Informatics, 1997


  Loading...