Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
Exploring Sparse Graphs with Advice (Extended Abstract)
verfasst von : Hans-Joachim Böckenhauer, Janosch Fuchs, Walter Unger
Erschienen in: Approximation and Online Algorithms
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Moving an autonomous agent through an unknown environment is one of the crucial problems for robotics and network analysis. Therefore, it received a lot of attention in the last decades and was analyzed in many different settings. The graph exploration problem is a theoretical and abstract model, where an algorithm has to decide how an agent, also called explorer, moves through a network with n vertices and m edges such that every point of interest is visited at least once. For its decisions, the knowledge of the algorithm is limited by the perception capacities of the explorer. We look at the fixed-graph scenario proposed by Kalyanasundaram and Pruhs (ICALP, 1993), where the explorer starts at a vertex of the network and sees all reachable vertices, their unique names and their distance from the current position.
Because the algorithm only learns the structure of the graph during computation, it cannot deterministically compute an optimal tour that visits every vertex at least once without prior knowledge. Therefore, we are interested in the amount of crucial a-priori information needed to solve the problem optimally, which we measure in terms of the well-studied model of advice complexity. Here, a deterministic algorithm can at any time access a binary advice tape written beforehand by an oracle that knows the optimal solution, the graph and the behavior of the algorithm. The number of bits read by the algorithm until the end of computation is called the advice complexity.
We look at the graph exploration problem on unknown directed graphs and focus on cyclic solutions. It is known that \(\mathcal {O}(n\log n)\) bits of advice are necessary and sufficient to compute an optimal solution, for general graphs. In this work, we present algorithms with an advice complexity of \(\mathcal {O}(m)\), thus improving the classical bound for sparse graphs.