Drawing maps with advice - Publikacja - MOST Wiedzy

Wyszukiwarka

Drawing maps with advice

Abstrakt

W pracy podejmujemy temat konstrukcji algorytmu dla agenta, który zostaje umieszczony w dowolnym wierzchołku grafu (wierzchołki są nierozróżnialne, krawędzie mają etykiety portów), po czym realizuje algorytm zmierzający do znalezienia drzewa spinającego grafu lub izomorficznej kopii grafu. Dla obu problemów podajemy asymptotycznie dokładne lub prawie dokładne oszacowania na ilość bitów dodatkowej informacji, którą agent musi otrzymać aby rozwiązanie problemu było możliwe.We study the problem of the amount of information required to draw a complete or a partial map of a graph with unlabeled nodes and arbitrarily labeled ports. A mobile agent, starting at any node of an unknown connected graph and walking in it, has to accomplish one of the following tasks: draw a complete map of the graph, i.e., find an isomorphic copy of it including port numbering, or draw a partial map, i.e., a spanning tree, again with port numbering. The agent executes a deterministic algorithm and cannot mark visited nodes in any way. None of these map drawing tasks is feasible without any additional information, unless the graph is a tree. This is due to the impossibility of recognizing already visited nodes. Hence we investigate the minimum number of bits of information (minimum size of advice) that has to be given to the agent to complete these tasks. It turns out that this minimum size of advice depends on the numbers n of nodes or the number m of edges of the graph, and on a crucial parameter μ, called the multiplicity of the graph, which measures the number of nodes that have an identical view of the graph.We give bounds on the minimum size of advice for both above tasks. For μ= 1 our bounds are asymptotically tight for both tasks and show that the minimum size of advice is very small: for an arbitrary function ϕ = ω(1) it suffices to give ϕ(n) bits of advice to accomplish both tasks for n-node graphs, and Θ(1) bits are not enough. For μ> 1 the minimum size of advice increases abruptly. In this case our bounds are asymptotically tight for topology recognition and asymptotically almost tight for spanning tree construction. We show that Θ(mlogμ) bits of advice are enough and necessary to recognize topology in the class of graphs with m edges and multiplicity μ> 1. For the second task we show that Ω(μlog(n/μ)) bits of advice are necessary and O (μlogn) bits of advice are enough to construct a spanning tree in the class of graphs with n nodes and multiplicity μ> 1. Thus in this case the gap between our bounds is always at most logarithmic, and the bounds are asymptotically tight for multiplicity μ = O(n α ), where α is any constant smaller than 1.

Cytowania

  • 2

    CrossRef

  • 0

    Web of Science

  • 3

    Scopus

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

Informacje szczegółowe

Kategoria:
Publikacja w czasopiśmie
Typ:
artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
Opublikowano w:
LECTURE NOTES IN COMPUTER SCIENCE strony 328 - 342,
ISSN: 0302-9743
Język:
angielski
Rok wydania:
2010
Opis bibliograficzny:
Dereniowski D., Pelc A.: Drawing maps with advice// LECTURE NOTES IN COMPUTER SCIENCE. -., nr. Nr 6343 (2010), s.328-342
DOI:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/978-3-642-15763-9_30
Weryfikacja:
Politechnika Gdańska

wyświetlono 14 razy

Publikacje, które mogą cię zainteresować

On extremal sizes of locally k-tree graphs

2010

Collision-Free Network Exploration

2014

On the size of identifying codes in triangle-free graphs

2012
Meta Tagi