 Home
 Search Results
 Page 1 of 1
Search for: All records

Total Resources2
 Resource Type

20
 Availability

20
 Author / Contributor
 Filter by Author / Creator


Kranakis, E. (2)

Krizanc, D. (2)

Narayanan, L. (2)

Pankratov, D. (2)

Shende, S. (2)

Czyzowicz, J (1)

Czyzowicz, J. (1)

Dobrev, S. (1)

Killick R. (1)

Killick, R. (1)

Opatrny, J (1)

Opatrny, J. (1)

#Tyler Phillips, Kenneth E. (0)

& AbreuRamos, E. D. (0)

& Ahmed, Khadija. (0)

& AkcilOkan, O. (0)

& Akuom, D. (0)

& Aleven, V. (0)

& AndrewsLarson, C. (0)

& Archibald, J. (0)

 Filter by Editor


& Spizer, S. M. (0)

& . Spizer, S. (0)

& Ahn, J. (0)

& Bateiha, S. (0)

& Bosch, N. (0)

& Chen, B. (0)

& Chen, Bodong (0)

& Drown, S. (0)

& Higgins, A. (0)

& Kali, Y. (0)

& RuizArias, P.M. (0)

& S. Spitzer (0)

& Spitzer, S. (0)

& Spitzer, S.M. (0)

:Chaosong Huang, Gang Lu (0)

A. Agarwal (0)

A. Beygelzimer (0)

A. E. Lischka (0)

A. E. Lischka, E. B. (0)

A. E. Lischka, E.B. Dyer (0)


Have feedback or suggestions for a way to improve these results?
!
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

We consider the problem of collective exploration of a known n node edgeweighted graph by k mobile agents that have limited energy but are capable of energy transfers. The agents are initially placed at an arbitrary subset of nodes in the graph, and each agent has an initial, possibly different, amount of energy. The goal of the exploration problem is for every edge in the graph to be traversed by at least one agent. The amount of energy used by an agent to travel distance x is proportional to x. In our model, the agents can share energy when colocated: when two agents meet, one can transfer part of its energy to the other. For an nnode path, we give an O(n+k) time algorithm that either nds an exploration strategy, or reports that one does not exist. For an nnode tree with l leaves, we give an O(n+lk^2) algorithm that finds an exploration strategy if one exists. Finally, for the general graph case, we show that the problem of deciding if exploration is possible by energysharing agents is NPhard, even for 3regular graphs. In addition, we show that it is always possible to find an exploration strategy if the totalmore »

Czyzowicz, J ; Killick R. ; Kranakis, E. ; Krizanc, D. ; Narayanan, L. ; Opatrny, J. ; Pankratov, D. ; Shende, S. ( , 32nd International Symposium on Algorithms and Computation (ISAAC 2021))We consider evacuation of a group of n ≥ 2 autonomous mobile agents (or robots) from an unknown exit on an infinite line. The agents are initially placed at the origin of the line and can move with any speed up to the maximum speed 1 in any direction they wish and they all can communicate when they are colocated. However, the agents have different wireless communication abilities: while some are fully wireless and can send and receive messages at any distance, a subset of the agents are senders, they can only transmit messages wirelessly, and the rest are receivers, they can only receive messages wirelessly. The agents start at the same time and their communication abilities are known to each other from the start. Starting at the origin of the line, the goal of the agents is to collectively find a target/exit at an unknown location on the line while minimizing the evacuation time, defined as the time when the last agent reaches the target. We investigate the impact of such a mixed communication model on evacuation time on an infinite line for a group of cooperating agents. In particular, we provide evacuation algorithms and analyze the resulting competitivemore »ratio (CR) of the evacuation time for such a group of agents. If the group has two agents of two different types, we give an optimal evacuation algorithm with competitive ratio CR = 3+2√2. If there is a single sender or fully wireless agent, and multiple receivers we prove that CR ∈ [2+√5,5], and if there are multiple senders and a single receiver or fully wireless agent, we show that CR ∈ [3,5.681319]. Any group consisting of only senders or only receivers requires competitive ratio 9, and any other combination of agents has competitive ratio 3.« less