Wyniki wyszukiwania dla: GRAPH EXPLORATION - MOST Wiedzy

Wyszukiwarka

Wyniki wyszukiwania dla: GRAPH EXPLORATION

Wyniki wyszukiwania dla: GRAPH EXPLORATION

  • 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

  • Graph Decomposition for Memoryless Periodic Exploration

    Publikacja

    - ALGORITHMICA - Rok 2012

    We consider a general framework in which a memoryless robot periodically explores all the nodes of a connected anonymous graph by following local information available at each vertex. For each vertex v, the endpoints of all edges adjacent to v are assigned unique labels within the range 1 to deg (v) (the degree of v). The generic exploration strategy is implemented using a right-hand-rule transition function: after entering vertex...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Multi-agent graph searching and exploration algorithms

    Publikacja

    - Rok 2020

    A team of mobile entities, which we refer to as agents or searchers interchangeably, starting from homebases needs to complete a given task in a graph.The goal is to build a strategy, which allows agents to accomplish their task. We analyze strategies for their effectiveness (e.g., the number of used agents, the total number of performed moves by the agents or the completion time).Currently, the fields of on-line (i.e., agents...

    Pełny tekst do pobrania w portalu

  • 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

  • Constructing a map of an anonymous graph: applications of universal sequences

    Publikacja

    - LECTURE NOTES IN COMPUTER SCIENCE - Rok 2010

    We study the problem of mapping an unknown environmentrepresented as an unlabelled undirected graph. A robot (or automaton)starting at a single vertex of the graph G has to traverse the graph and return to its starting point building a map of the graph in the process. We are interested in the cost of achieving this task (whenever possible) in terms of the number of edge traversal made by the robot. Another optimization criteria...

    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

  • How to meet when you forget: log-space rendezvous in arbitrary graphs

    Publikacja

    - DISTRIBUTED COMPUTING - Rok 2011

    Two identical (anonymous) mobile agents start from arbitrary nodes in an a priori unknown graph and move synchronously from node to node with the goal of meeting. This rendezvous problem has been thoroughly studied, both for anonymous and for labeled agents, along with another basic task, that of exploring graphs by mobile agents. The rendezvous problem is known to be not easier than graph exploration. A well-known recent result...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Brief Announcement: Energy Constrained Depth First Search

    Publikacja

    - Rok 2018

    Depth first search is a natural algorithmic technique for constructing a closed route that visits all vertices of a graph. The length of such route equals, in an edge-weighted tree, twice the total weight of all edges of the tree and this is asymptotically optimal over all exploration strategies. This paper considers a variant of such search strategies where the length of each route is bounded by a positive integer B (e.g. due...

    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 portalu

  • Distributed graph searching with a sense of direction

    In this work we consider the edge searching problem for vertex-weighted graphs with arbitrarily fast and invisible fugitive. The weight function w provides for each vertex v the minimum number of searchers required to guard v, i.e., the fugitive may not pass through v without being detected only if at least w(v) searchers are present at v. This problem is a generalization of the classical edge searching problem, in which one has...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • How to meet when you forget: log-space rendezvous in arbitrary graphs

    Publikacja

    - DISTRIBUTED COMPUTING - Rok 2012

    Problem rendezvous został dogłębnie zbadany, zarówno dla agendów anonimowych jak i poetykietowanych. zbadano też problem eksploracji grafu za pomocą agentów mobilnych.

    Pełny tekst do pobrania w serwisie zewnętrznym