SOFSEM 2019: Theory and Practice of Computer Science
45th International Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 27-30, 2019, Proceedings
Page
%P
14 Result(s)
within
Rastislav Královič
Algorithm Analysis and Problem Complexity
Data Structures
-
Book and Conference Proceedings
-
Chapter and Conference Paper
Edge-Editing to a Dense and a Sparse Graph Class
We consider a graph edge-editing problem, where the goal is to transform a given graph G into a disjoint union of two graphs from a pair of given graph classes, investigating what properties of the classes make t...
-
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 ...
-
Chapter and Conference Paper
Advice Complexity: Quantitative Approach to A-Priori Information
We survey recent results from different areas, studying how introducing per-instance a-priori information affects the solvability and complexity of given tasks. We mainly focus on distributed, and online compu...
-
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...
-
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...
-
Chapter and Conference Paper
Black Hole Search in Directed Graphs
We consider the problem of cooperative network exploration by agents under the assumption that there is a harmful host present in the network that destroys the incoming agents without outside trace – the so-ca...
-
Chapter and Conference Paper
Periodic Data Retrieval Problem in Rings Containing a Malicious Host
In the problems of exploration of faulty graphs, a team of cooperating agents is considered moving in a network containing one or more nodes that can harm the agents. A most notable among these problems is the pr...
-
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...
-
Chapter and Conference Paper
Online Bandwidth Allocation
The paper investigates a version of the resource allocation problem arising in the wireless networking, namely in the OVSF code reallocation process. In this setting a complete binary tree of a given height n is ...
-
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 ...
-
Book and Conference Proceedings
Mathematical Foundations of Computer Science 2006
31st International Symposium, MFCS 2006, Stará Lesná, Slovakia, August 28-September 1, 2006. Proceedings
-
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...
-
Chapter and Conference Paper
On Semi-perfect 1-Factorizations
The perfect 1-factorization conjecture by A. Kotzig [7] asserts the existence of a 1-factorization of a complete graph K 2n in which any two 1-factors induce a Hamiltonian cycle. This conject...
