Exploring sparse graphs with advice

Autor: Hans-Joachim Böckenhauer, Janosch Fuchs, Walter Unger
Jazyk: angličtina
Rok vydání: 2022
Předmět:
Zdroj: Information and Computation, 289 (Part A)
ISSN: 0890-5401
Popis: Graph exploration is a theoretical model of the crucial task of moving an agent through an unknown environment. Here, an algorithm has to guide an explorer through a network with n vertices and m edges, visiting every vertex at least once. We consider the fixed-graph scenario by Kalyanasundaram and Pruhs (ICALP, 1993), where the explorer sees all vertices reachable in one step, their unique names and their distance from the current position. The algorithm only learns the structure of the graph during computation. Therefore, we are interested in the amount of crucial a-priori information (the advice complexity) needed to solve the problem optimally. We look at graph exploration on directed graphs and focus on cyclic solutions. It is known that O(n log n) bits of advice are necessary and sufficient to compute an optimal solution for general graphs. We present algorithms with O(m) advice, thus improving the bound for sparse graphs.
Information and Computation, 289 (Part A)
ISSN:0890-5401
Databáze: OpenAIRE
Externí odkaz: