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
-
Article
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 randomize...
-
Chapter and Conference Paper
Two-Way Non-uniform Finite Automata
We consider two-tape automata where one tape contains the input word w, and the other contains an advice string \(\alpha (|w|)\) ...
-
Chapter and Conference Paper
Improved Lower Bounds for Shoreline Search
Shoreline search is a natural and well-studied generalisation of the classical cow-path problem: k initially co-located unit speed agents are searching for a line (called shoreline) in 2 dimensional Euclidean spa...
-
Chapter and Conference Paper
Exploration of Time-Varying Connected Graphs with Silent Agents
Exploration is a fundamental task in mobile computing. We study the version where a group of cooperating agents is situated in a graph, and the task is to make sure that every vertex of the graph is visited by...
-
Book and Conference Proceedings
-
Chapter
Determinism and Nondeterminism in Finite Automata with Advice
We consider the model of finite automata with advice introduced by Küçük et al. We show that there are languages, in particular the language of palindromes, that cannot be recognized by
-
Chapter and Conference Paper
The Complexity of Paging Against a Probabilistic Adversary
We consider deterministic online algorithms for paging. The offline version of the paging problem, in which the whole input is given in advance, is known to be easily solvable. If the input is random, chosen a...
-
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
Disjoint Path Allocation with Sublinear Advice
We study the disjoint path allocation problem. In this setting, a path \(P\) ...
-
Article
Advice Complexity of Maximum Independent set in Sparse and Bipartite Graphs
We study the advice complexity of the online version of the Maximum Independent Set problem, restricted to the sparse, and bipartite graphs, respectively. We show that for sparse graphs, constant-sized advice ...
-
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
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....
-
Chapter and Conference Paper
Determinism vs. Nondeterminism for Two-Way Automata
The question whether nondeterminism is more powerful than determinism for two-way automata is one of the most famous old open problems on the border between formal language theory and automata theory. An expon...
-
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
On the Advice Complexity of the k-Server Problem
Competitive analysis is the established tool for measuring the output quality of algorithms that work in an online environment. Recently, the model of advice complexity has been introduced as an alternative measu...
-
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
Information Complexity of Online Problems
What is information? Frequently spoken about in many contexts, yet nobody has ever been able to define it with mathematical rigor. The best we are left with so far is the concept of entropy by Shannon, and the...
