Skip to main content

8 Result(s)

within Rastislav Královič Remove this filter Algorithm Analysis and Problem Complexity Remove this filter Algorithms Remove this filter

and

  1. Article

    Open Access

    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 randomize...

    Dennis Komm, Rastislav Královič, Richard Královič, Tobias Mömke in Algorithmica (2022)

    Download PDF (443 KB) View Article

  2. No Access

    Chapter and Conference Paper

    Treasure Hunt with Advice

    The node searching problem (a.k.a. treasure hunt) is a fundamental task performed by mobile agents in a network and can be viewed as an online version of the shortest path problem: an agent starts in a vertex ...

    Dennis Komm, Rastislav Královič… in Structural Information and Communication C… (2015)

  3. No Access

    Chapter and Conference Paper

    Independent Set with Advice: The Impact of Graph Knowledge

    We are interested in online graph problems where the knowledge of the underlying graph G (all arriving vertices are from G) has a profound impact on the size of the advice needed to solve the problem efficiently....

    Stefan Dobrev, Rastislav Královič, Richard Královič in Approximation and Online Algorithms (2013)

  4. No Access

    Chapter and Conference Paper

    Online Graph Exploration with Advice

    We study the problem of exploring an unknown undirected graph with non-negative edge weights. Starting at a distinguished initial vertex s, an agent must visit every vertex of the graph and return to s. Upon visi...

    Stefan Dobrev, Rastislav Královič… in Structural Information and Communication C… (2012)

  5. No Access

    Chapter and Conference Paper

    Routing in Carrier-Based Mobile Networks

    The past years have seen an intense research effort directed at study of delay/disruption tolerant networks and related concepts (intermittently connected networks, opportunistic mobility networks). As a funda...

    Bronislava Brejová, Stefan Dobrev… in Structural Information and Communication C… (2011)

  6. No Access

    Chapter and Conference Paper

    On the Advice Complexity of Online Problems

    In this paper, we investigate to what extent the solution quality of online algorithms can be improved by allowing the algorithm to extract a given amount of information about the input. We consider the recent...

    Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královič… in Algorithms and Computation (2009)

  7. No Access

    Chapter and Conference Paper

    Rapid Almost-Complete Broadcasting in Faulty Networks

    This paper studies the problem of broadcasting in synchronous point-to-point networks, where one initiator owns a piece of information that has to be transmitted to all other vertices as fast as possible. The ...

    Rastislav Královič, Richard Královič in Structural Information and Communication Complexity (2007)

  8. No Access

    Chapter and Conference Paper

    On Fractional Dynamic Faults with Threshold

    Unlike localized communication failures that occur on a fixed (although a priori unknown) set of links, dynamic faults can occur on any link. Known also as mobile or ubiquitous faults, their presence makes many t...

    Stefan Dobrev, Rastislav Královič… in Structural Information and Communication C… (2006)