Wyniki wyszukiwania dla: eksploracja grafow - MOST Wiedzy

Wyszukiwarka

Wyniki wyszukiwania dla: eksploracja grafow

Wyniki wyszukiwania dla: eksploracja grafow

  • Synchronization helps robots to detect black holes in directed graphs

    Publikacja

    - Rok 2009

    Praca zawiera nowe wyniki dla problemu poszukiwania czarnej dziury w grafie skierowanym przez zbiór agentów. Czarna dziura jest węzłem niszczącym wszystkich wchodzącej do niej agentów. Pokazano, że w przypadku, gdy stopień wejściowy czarnej dziury wynosi D, do przeszukania grafu skierowanego w modelu synchronicznym wystarcza O(D 2^D) agentów. Wartość ta jest bliska znanemu z literatury oszacowaniu dolnemu Omega (2^D). W pracy pokazano...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Euler tour lock-in problem in the rotor-router model

    Publikacja
    • E. Bampas
    • L. Gąsieniec
    • N. Hanusse
    • D. Ilcinkas
    • R. Klasing
    • A. Kosowski

    - Rok 2009

    W pracy rozważano model eksploracji grafu nieskierowanego przez pojedynczego agenta, w którym sterowanie agentem odbywa się zgodnie z zasadą ''rotor-router'' (inaczej: ''Propp machine''). Porównano czas stabilizacji agenta do trajektorii w postaci cyklu Eulera dla różnych klas grafów, prowadząc rozważania w kontekście teorii gier. Przydział początkowych portów i wskaźników w modelu jest traktowany jako rozgrywka pomiędzy graczem...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Robustness of the Rotor-router Mechanism

    Publikacja

    - Rok 2009

    W pracy rozważano model eksploracji grafu nieskierowanego przez pojedynczego agenta, w którym sterowanie agentem odbywa się zgodnie z zasadą ''rotor-router'' (inaczej: ''Propp machine''). Przeanalizowano czas stabilizacji agenta do trajektorii w postaci cyklu Eulera w przypadku wystąpienia zaburzeń w grafie: usunięcie krawędzi, dodanie krawędzi, lokalna zamiana portów

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Graph decomposition for improving memoryless periodic exploration

    Publikacja

    - Rok 2009

    W ostatnich latach często badanym problem jest eksploracja anonimowych grafów z lokalnymi etykietami portów przy każdym wierzchołku. Niedawno pokazano [Czyzowicz et al., Proc. SIROCCO'09], że dla każdego grafu istnieje poetykietowanie prowadzące do eksploracji przez automat bezpamięciowy z okresem co najwyżej 13n/3. W niniejszej pracy poprawiamy to ograniczenie do 4n-2, stosując całkowicie nową technikę dekompozycji grafu.

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Derandomizing random walks in undirected graphs using locally fair exploration strategies

    Publikacja

    - Rok 2009

    W pracy rozważono problem eksploracji anonimowego nieskierowanego grafu przez bezpamięciowego robota. Zaprojektowane strategie eksploracji cechują się własnością lokalnej sprawiedliwości, tj. kolejne krawędzie trawersowane przez robota wybierane są na podstawie lokalnych informacji tak, aby zapewnić równomierne wykorzystanie krawędzi w sensie pewnego kryterium. Okazuje się, że odpowiedni dobór kryterium jest kluczowy do zapewnienia...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Collision-Free Network Exploration

    Publikacja
    • J. Czyzowicz
    • D. Dereniowski
    • L. Gąsieniec
    • R. Klasing
    • A. Kosowski
    • D. Pająk

    - Rok 2014

    A set of mobile agents is placed at different nodes of a n-node network. The agents synchronously move along the network edges in a collision-free way, i.e., in no round may two agents occupy the same node. In each round, an agent may choose to stay at its currently occupied node or to move to one of its neighbors. An agent has no knowledge of the number and initial positions of other agents. We are looking for the shortest possible...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Fast collaborative graph exploration

    Publikacja

    - INFORMATION AND COMPUTATION - Rok 2015

    We study the following scenario of online graph exploration. A team of k agents is initially located at a distinguished vertex r of an undirected graph. At every time step, each agent can traverse an edge of the graph. All vertices have unique identifiers, and upon entering a vertex, an agent obtains the list of identifiers of all its neighbors. We ask how many time steps are required to complete exploration, i.e., to make sure...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Fast Collaborative Graph Exploration

    Publikacja

    - LECTURE NOTES IN COMPUTER SCIENCE - Rok 2013

    We study the following scenario of online graph exploration. A team of k agents is initially located at a distinguished vertex r of an undirected graph. At every time step, each agent can traverse an edge of the graph. All vertices have unique identifiers, and upon entering a vertex, an agent obtains the list of identifiers of all its neighbors. We ask how many time steps are required to complete exploration, i.e., to make sure...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Drawing maps with advice

    Rozważamy następujący problem obliczeniowy. Agent zostaje umieszczony w wierzchołku nieznanego mu grafu. Wierzchołki grafu są nierozróżnialne, natomiast krawędzie posiadają numery portów. Zadaniem agenta jest wyznaczenie mapy, tzn. obliczenie izomorficznej kopii grafu, lub obliczenie dowolnego drzewa spinającego grafu. Bez dodatkowej informacji zadań tych nie można wykonać. W artykule wyznaczamy oszacowania na minimalną liczbę...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Synchronous black hole search in directed graphs

    Publikacja

    - THEORETICAL COMPUTER SCIENCE - Rok 2011

    The paper considers a team of robots which has to explore a graph G, where some nodes can be harmful. Robots are initially located at the so-called home base node. The dangerous nodes are the so-called black hole nodes, and once a robot enters in one of them, it is destroyed. The goal is to find a strategy in order to explore G in such a way that minimum number of robots is wasted. The exploration ends if there is at least one...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Drawing maps with advice

    Publikacja

    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ć...

    Pełny tekst do pobrania w serwisie zewnętrznym