43 results on '"Labourel, Arnaud"'
Search Results
2. Distance and Routing Labeling Schemes for Cube-Free Median Graphs
- Author
-
Chepoi, Victor, Labourel, Arnaud, and Ratel, Sébastien
- Published
- 2021
- Full Text
- View/download PDF
3. On density of subgraphs of halved cubes
- Author
-
Chepoi, Victor, Labourel, Arnaud, and Ratel, Sébastien
- Published
- 2019
- Full Text
- View/download PDF
4. Almost-Optimal Deterministic Treasure Hunt in Unweighted Graphs.
- Author
-
BOUCHARD, SÉBASTIEN, DIEUDONNÉ, YOANN, LABOUREL, ARNAUD, and PELC, ANDRZEJ
- Subjects
KNOWLEDGE graphs ,FUEL tanks ,GRAPH connectivity ,TRAVELING salesman problem - Abstract
A mobile agent navigating along edges of a simple connected unweighted graph, either finite or countably infinite, has to find an inert target (treasure) hidden in one of the nodes. This task is known as treasure hunt. The agent has no a priori knowledge of the graph, of the location of the treasure, or of the initial distance to it. The cost of a treasure hunt algorithm is the worst-case number of edge traversals performed by the agent until finding the treasure. Awerbuch et al. [3] considered graph exploration and treasure hunt for finite graphs in a restricted model where the agent has a fuel tank that can be replenished only at the starting node s. The size of the tank is B = 2(1 + a)r, for some positive real constant a, where r, called the radius of the graph, is the maximum distance from s to any other node. The tank of size B allows the agent to make at most -B° edge traversals between two consecutive visits at node s. Let e (d) be the number of edges whose at least one endpoint is at distance less than d from s. Awerbuch et al. [3] conjectured that it is impossible to find a treasure hidden in a node at distance at most d at cost nearly linear in e (d). We first design a deterministic treasure hunt algorithm working in the model without any restrictions on the moves of the agent at cost O(e (d) logd) and then show how to modify this algorithm to work in the model from Awerbuch et al. [3] with the same complexity. Thus, we refute the preceding 20-year-old conjecture. We observe that no treasure hunt algorithm can beat cost T(e (d)) for all graphs, and thus our algorithms are also almost optimal. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
5. Tell Me Where I Am So I Can Meet You Sooner : (Asynchronous Rendezvous with Location Information)
- Author
-
Collins, Andrew, Czyzowicz, Jurek, Gąsieniec, Leszek, Labourel, Arnaud, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Abramsky, Samson, editor, Gavoille, Cyril, editor, Kirchner, Claude, editor, Meyer auf der Heide, Friedhelm, editor, and Spirakis, Paul G., editor
- Published
- 2010
- Full Text
- View/download PDF
6. Tight bounds for black hole search with scattered agents in synchronous rings
- Author
-
Chalopin, Jérémie, Das, Shantanu, Labourel, Arnaud, and Markou, Euripides
- Published
- 2013
- Full Text
- View/download PDF
7. Rendezvous in networks in spite of delay faults
- Author
-
Chalopin, Jérémie, Dieudonné, Yoann, Labourel, Arnaud, and Pelc, Andrzej
- Published
- 2016
- Full Text
- View/download PDF
8. Convergecast and Broadcast by Power-Aware Mobile Agents
- Author
-
Anaya, Julian, Chalopin, Jérémie, Czyzowicz, Jurek, Labourel, Arnaud, Pelc, Andrzej, and Vaxès, Yann
- Published
- 2016
- Full Text
- View/download PDF
9. Worst-case optimal exploration of terrains with obstacles
- Author
-
Czyzowicz, Jurek, Ilcinkas, David, Labourel, Arnaud, and Pelc, Andrzej
- Published
- 2013
- Full Text
- View/download PDF
10. Robustness of Distances and Diameter in a Fragile Network
- Author
-
Casteigts, Arnaud, Corsini, Timothée, Hocquard, Hervé, and Labourel, Arnaud
- Subjects
Series-parallel graphs ,Rooted minors ,Mathematics of computing → Paths and connectivity problems ,Dynamic networks ,Networks → Network dynamics ,Longest path ,Theory of computation → Complexity classes - Abstract
A property of a graph G is robust if it remains unchanged in all connected spanning subgraphs of G. This form of robustness is motivated by networking contexts where some links eventually fail permanently, and the network keeps being used so long as it is connected. It is then natural to ask how certain properties of the network may be impacted as the network deteriorates. In this paper, we focus on two particular properties, which are the diameter, and pairwise distances among nodes. Surprisingly, the complexities of deciding whether these properties are robust are quite different: deciding the robustness of the diameter is coNP-complete, whereas deciding the robustness of the distance between two given nodes has a linear time complexity. This is counterintuitive, because the diameter consists of the maximum distance over all pairs of nodes, thus one may expect that the robustness of the diameter reduces to testing the robustness of pairwise distances. On the technical side, the difficulty of the diameter is established through a reduction from hamiltonian paths. The linear time algorithm for deciding robustness of the distance relies on a new characterization of two-terminal series-parallel graphs (TTSPs) in terms of excluded rooted minor, which may be of independent interest., LIPIcs, Vol. 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022), pages 9:1-9:16
- Published
- 2022
- Full Text
- View/download PDF
11. Optimality and competitiveness of exploring polygons by mobile robots
- Author
-
Czyzowicz, Jurek, Labourel, Arnaud, and Pelc, Andrzej
- Published
- 2011
- Full Text
- View/download PDF
12. Asynchronous deterministic rendezvous in bounded terrains
- Author
-
Czyzowicz, Jurek, Ilcinkas, David, Labourel, Arnaud, and Pelc, Andrzej
- Published
- 2011
- Full Text
- View/download PDF
13. Impact of knowledge on the cost of treasure hunt in trees.
- Author
-
Bouchard, Sébastien, Labourel, Arnaud, and Pelc, Andrzej
- Subjects
DETERMINISTIC algorithms ,TREES ,COST - Abstract
Treasure hunt is finding a hidden inert target by a mobile agent. We consider deterministic algorithms for treasure hunt in trees. Our goal is to establish the impact of different kinds of initial knowledge given to the agent on the cost of treasure hunt, defined as the total number of edge traversals until the agent reaches the treasure. The agent can be initially given either a complete map of the tree rooted at its starting node, with all port numbers marked, or a blind map of the tree rooted at its starting node but without port numbers. It may also be given, or not, the distance from the root to the treasure. This yields four different knowledge types that are partially ordered by their precision. The penalty of a less precise knowledge type 풯2 over a more precise knowledge type 풯1 measures intuitively the worst‐case ratio of the cost of an algorithm supplied with knowledge of type 풯2 over the cost of an algorithm supplied with knowledge of type 풯1. Our main results establish penalties for comparable knowledge types in this partial order. For knowledge types with known distance, the penalty for having a blind map over a complete map turns out to be very large. By contrast, for unknown distance, the penalty of having a blind map over having a complete map is small. When a map is provided (either complete or blind), the penalty of not knowing the distance over knowing it is medium. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
14. Collaborative Delivery on a Fixed Path with Homogeneous Energy-Constrained Agents
- Author
-
Chalopin, Jérémie, Das, Shantanu, Disser, Yann, Labourel, Arnaud, Mihalák, Matúš, Censor-Hillel, Keren, Flammini, Michele, Algorithmique Distribuée (DALGO), Laboratoire d'Informatique et Systèmes (LIS), Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU), Technische Universität Darmstadt (TU Darmstadt), Department of data science and Knowledge Engineering [Maastricht], Maastricht University [Maastricht], ANR-14-CE36-0002,ANCOR,Algorithm Design for Microrobots with Energy Constraints(2014), DKE Scientific staff, RS: FSE DACS NSO, Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Technische Universität Darmstadt - Technical University of Darmstadt (TU Darmstadt), Department of Data Science and Knowledge Engineering, Maastricht University, Aix Marseille Univ, Université de Toulon, CNRS, LIS, Marseille, France, Graduate School CE, TU Darmstadt, Dept. of Advanced Computing Sciences, RS: FSE DACS, and RS: FSE DACS Mathematics Centre Maastricht
- Subjects
Vertex (graph theory) ,Mathematical optimization ,Schedule ,Traverse ,General Computer Science ,Computer science ,Distributed computing ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,0102 computer and information sciences ,02 engineering and technology ,Hardness of approximation ,01 natural sciences ,Theoretical Computer Science ,Collaborative delivery ,Energy constrained ,0202 electrical engineering, electronic engineering, information engineering ,Fixed path ,Time complexity ,ComputingMilieux_MISCELLANEOUS ,Approximation algorithm ,Directed graph ,Energy constrained robots ,Approximation algorithms ,Computer Science::Multiagent Systems ,Homogeneous ,010201 computation theory & mathematics ,Bounded function ,Path (graph theory) ,Graph (abstract data type) ,020201 artificial intelligence & image processing ,Mobile agents ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,Directed graphs - Abstract
We consider the problem of collectively delivering a package from a specified source to a designated target location in a graph, using multiple mobile agents. Each agent starts from a distinct vertex of the graph, and can move along the edges of the graph carrying the package. However, each agent has limited energy budget allowing it to traverse a path of bounded length b; thus, multiple agents need to collaborate to move the package to its destination. Given the positions of the agents in the graph and their energy budgets, the problem of finding a feasible movement schedule is called the collaborative delivery problem and has been studied before.one of the open questions from previous results is what happens when the delivery must follow a fixed path given in advance. Although this special constraint reduces the search space for feasible solutions, the problem of finding a feasible schedule remains np hard (as the original problem). We consider the optimization version of the problem that asks for the optimal energy budget b per agent which allows for a feasible delivery schedule, given the initial positions of the agents. We show the existence of better approximations for the fixed-path version of the problem (at least for the restricted case of single pickup per agent), compared to the known results for the general version of the problem, thus answering the open question from the previous paper.we provide polynomial time approximation algorithms for both directed and undirected graphs, and establish hardness of approximation for the directed case. Note that the fixed path version of collaborative delivery requires completely different techniques since a single agent may be used multiple times, unlike the general version of collaborative delivery studied before. We show that restricting each agent to a single pickup allows better approximations for fixed path collaborative delivery compared to the original problem. Finally, we provide a polynomial time algorithm for determining a feasible delivery strategy, if any exists, for a given budget b when the number of available agents is bounded by a constant.
- Published
- 2019
15. Distance Labeling Schemes for Cube-Free Median Graphs
- Author
-
Chepoi, Victor, Labourel, Arnaud, Ratel, Sébastien, Algorithmique, Combinatoire et Recherche Opérationnelle (ACRO), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Algorithmique Distribuée (DALGO), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), and ANR-17-CE40-0015,DISTANCIA,Théorie métrique des graphes(2017)
- Subjects
060201 languages & linguistics ,000 Computer science, knowledge, general works ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,06 humanities and the arts ,02 engineering and technology ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] ,ComputingMethodologies_PATTERNRECOGNITION ,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] ,0602 languages and literature ,Computer Science ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,[MATH.MATH-MG]Mathematics [math]/Metric Geometry [math.MG] ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
International audience; Distance labeling schemes are schemes that label the vertices of a graph with short labels in such away that the distance between any two vertices u and v can be determined efficiently by merelyinspecting the labels of u and v, without using any other information. One of the important problemsis finding natural classes of graphs admitting distance labeling schemes with labels of polylogarithmicsize. In this paper, we show that the class of cube-free median graphs on n nodes enjoys distancelabeling scheme with labels of O(log3 n) bits.
- Published
- 2019
- Full Text
- View/download PDF
16. On density of subgraphs of Cartesian products.
- Author
-
Chepoi, Victor, Labourel, Arnaud, and Ratel, Sébastien
- Subjects
- *
GRAPH connectivity , *MATROIDS , *DENSITY , *MANUFACTURED products - Abstract
In this paper, we extend two classical results about the density of subgraphs of hypercubes to subgraphs G of Cartesian products G1□⋯□Gm of arbitrary connected graphs. Namely, we show that (∣E(G)|/∣V(G)∣)≤⌈2max{dens(G1),...,dens(Gm)}⌉log∣V(G)∣, where dens(H) is the maximum ratio ∣E(H′)∣/∣V(H′)∣ taken over all subgraphs H′ of H. We introduce the notions of VC‐dimension VC‐dim(G) and VC‐density VC‐dens(G) of a subgraph G of a Cartesian product G1□⋯□Gm, generalizing the classical Vapnik‐Chervonenkis dimension of set‐families (viewed as subgraphs of hypercubes). We prove that if G1,...,Gm belong to the class G(H) of all finite connected graphs not containing a given graph H as a minor, then for any subgraph G of G1□⋯□Gm the sharper inequality (∣E(G)∣/∣V(G)∣)≤μ(H)⋅VC‐dim*(G) holds, where μ(H) is the supremum of the densities of the graphs from G(H). We refine and sharpen these two results to several specific graph classes. We also derive upper bounds (some of them polylogarithmic) for the size of adjacency labeling schemes of subgraphs of Cartesian products. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
17. Lock-in Problem for Parallel Rotor-router Walks
- Author
-
Chalopin, Jérémie, Das, Shantanu, Gawrychowski, Pawel, Kosowski, Adrian, Labourel, Arnaud, Uznanski, Przemyslaw, Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft, Networks, Graphs and Algorithms (GANG), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Department of Information and Computer Science [Aalto], Helsinki Institute for Information Technology (HIIT), Helsingin yliopisto = Helsingfors universitet = University of Helsinki-Aalto University-Helsingin yliopisto = Helsingfors universitet = University of Helsinki-Aalto University, Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), and Aalto University-University of Helsinki-Aalto University-University of Helsinki
- Subjects
FOS: Computer and information sciences ,Discrete Mathematics (cs.DM) ,Computer Science - Data Structures and Algorithms ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Data Structures and Algorithms (cs.DS) ,Computer Science - Discrete Mathematics - Abstract
The rotor-router model, also called the Propp machine, was introduced as a deterministic alternative to the random walk. In this model, a group of identical tokens are initially placed at nodes of the graph. Each node maintains a cyclic ordering of the outgoing arcs, and during consecutive turns the tokens are propagated along arcs chosen according to this ordering in round-robin fashion. The behavior of the model is fully deterministic. Yanovski et al.(2003) proved that a single rotor-router walk on any graph with m edges and diameter $D$ stabilizes to a traversal of an Eulerian circuit on the set of all 2m directed arcs on the edge set of the graph, and that such periodic behaviour of the system is achieved after an initial transient phase of at most 2mD steps. The case of multiple parallel rotor-routers was studied experimentally, leading Yanovski et al. to the conjecture that a system of $k \textgreater{} 1$ parallel walks also stabilizes with a period of length at most $2m$ steps. In this work we disprove this conjecture, showing that the period of parallel rotor-router walks can in fact, be superpolynomial in the size of graph. On the positive side, we provide a characterization of the periodic behavior of parallel router walks, in terms of a structural property of stable states called a subcycle decomposition. This property provides us the tools to efficiently detect whether a given system configuration corresponds to the transient or to the limit behavior of the system. Moreover, we provide polynomial upper bounds of $O(m^4 D^2 + mD \log k)$ and $O(m^5 k^2)$ on the number of steps it takes for the system to stabilize. Thus, we are able to predict any future behavior of the system using an algorithm that takes polynomial time and space. In addition, we show that there exists a separation between the stabilization time of the single-walk and multiple-walk rotor-router systems, and that for some graphs the latter can be asymptotically larger even for the case of $k = 2$ walks.
- Published
- 2015
18. Retracts of Products of Chordal Graphs
- Author
-
Bresar, Bostjan, Chalopin, Jérémie, Chepoi, Victor, Kovse, Matjaz, Labourel, Arnaud, Vaxès, Yann, Faculty of Natural Sciences and Mathematics [Maribor], University of Maribor, Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), and Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
[INFO]Computer Science [cs] - Abstract
International audience; In this article, we characterize the graphs $G$ that are the retracts of Cartesian products of chordal graphs. We show that they are exactly the weakly modular graphs that do not contain $K_{2, 3}$, the $4$-wheel minus one spoke $W_4^{-}$, and the $k$-wheels $W_k$ (for $k\geq 4$) as induced subgraphs. We also show that these graphs $G$ are exactly the cage-amalgamation graphs as introduced by Brešar and Tepeh Horvat (Cage-amalgamation graphs, a common generalization of chordal and median graphs, Eur J Combin 30 (2009), 1071–1081); this solves the open question raised by these authors. Finally, we prove that replacing all products of cliques of $G$ by products of Euclidean simplices, we obtain a polyhedral cell complex which, endowed with an intrinsic Euclidean metric, is a CAT(0) space. This generalizes similar results about median graphs as retracts of hypercubes (products of edges) and median graphs as 1-skeletons of CAT(0) cubical complexes.
- Published
- 2013
19. Tight Bounds for Black Hole Search with Scattered Agents in Synchronous Rings
- Author
-
Chalopin, Jérémie, Das, Shantanu, Labourel, Arnaud, Markou, Euripides, Laboratoire d'informatique Fondamentale de Marseille - UMR 6166 (LIF), Université de la Méditerranée - Aix-Marseille 2-Université de Provence - Aix-Marseille 1-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science & Biomedical Informatics [Galaneika], University of Thessaly [Volos] (UTH), and ANR-08-VERS-0015,SHAMAN,Architectures auto-* pour les réseaux adverses et malicieux(2008)
- Subjects
General Relativity and Quantum Cosmology ,Anonymous Networks ,[INFO.INFO-MA]Computer Science [cs]/Multiagent Systems [cs.MA] ,Astrophysics::High Energy Astrophysical Phenomena ,Black Hole Search ,Fault Tolerance ,Identical tokens ,Finite State Automata ,Distributed Algorithms ,Mobile Agents - Abstract
We study the problem of locating a particularly dangerous node, the so-called black hole in a synchronous anonymous ring network with mobile agents. A black hole is a harmful stationary process residing in a node of the network and destroying destroys all mobile agents visiting that node without leaving any trace. We consider the more challenging scenario when the agents are identical and initially scattered within the network. Moreover, we solve the problem with agents that have constant-sized memory and carry a constant number of identical tokens, which can be placed at nodes of the network. In contrast, the only known solutions for the case of scattered agents searching for a black hole, use stronger models where the agents have non-constant memory, can write messages in whiteboards located at nodes or are allowed to mark both the edges and nodes of the network with tokens. This paper solves the problem for ring networks containing a single black hole. We are interested in the minimum resources (number of agents and tokens) necessary for locating all links incident to the black hole. We present deterministic algorithms for ring topologies and provide matching lower and upper bounds for the number of agents and the number of tokens required for deterministic solutions to the black hole search problem, in oriented or unoriented rings, using movable or unmovable tokens.
- Published
- 2011
20. Tell Me Where I Am So I Can Meet You Sooner
- Author
-
Collins, Andrew, Czyzowicz, Jurek, Gąsieniec, Leszek, Labourel, Arnaud, Department of Computer Science [Liverpool], University of Liverpool, Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), and Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU)
- Subjects
Computer Science::Multiagent Systems ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] - Abstract
International audience; In this paper we study efficient rendezvous of two mobile agents moving asynchronously in the Euclidean 2d-space. Each agent has limited visibility, permitting it to see its neighborhood at unit range from its current location. Moreover, it is assumed that each agent knows its own initial position in the plane given by its coordinates. The agents, however, are not aware of each others position. The agents possess coherent compasses and the same unit of length, which permit them to consider their current positions within the same system of coordinates. The cost of the rendezvous algorithm is the sum of lengths of the trajectories of both agents. This cost is taken as the maximum over all possible asynchronous movements of the agents, controlled by the adversary. We propose an algorithm that allows the agents to meet in a local neighborhood of diameter O(d), where d is the original distance between the agents. This seems rather surprising since each agent is unaware of the possible location of the other agent. In fact, the cost of our algorithm is O(d 2 + ε ), for any constant ε> 0. This is almost optimal, since a lower bound of Ω(d 2) is straightforward. The only up to date paper [12] on asynchronous rendezvous of bounded-visibility agents in the plane provides the feasibility proof for rendezvous, proposing a solution exponential in the distance d and in the labels of the agents. In contrast, we show here that, when the identity of the agent is based solely on its original location, an almost optimal solution is possible. An integral component of our solution is the construction of a novel type of non-simple space-filling curves that preserve locality. An infinite curve of this type visits specific grid points in the plane and provides a route that can be adopted by the mobile agents in search for one another. This new concept may also appear counter-intuitive in view of the result from [22] stating that for any simple space-filling curve, there always exists a pair of close points in the plane, such that their distance along the space-filling curve is arbitrarily large.
- Published
- 2010
21. Collaborative Delivery with Energy-Constrained Mobile Robots.
- Author
-
Bärtschi, Andreas, Chalopin, Jérémie, Das, Shantanu, Disser, Yann, Geissmann, Barbara, Graf, Daniel, Labourel, Arnaud, and Mihalák, Matúš
- Published
- 2016
- Full Text
- View/download PDF
22. Brief Announcement: On Local Representation of Distances in Trees
- Author
-
Gavoille, Cyril, Labourel, Arnaud, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), INRIA Futurs, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest
- Subjects
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,ComputingMilieux_MISCELLANEOUS - Abstract
International audience
- Published
- 2007
23. Limit Behavior of the Multi-agent Rotor-Router System.
- Author
-
Chalopin, Jěrémie, Das, Shantanu, Gawrychowski, Paweı, Kosowski, Adrian, Labourel, Arnaud, and Uznański, Przemysław
- Published
- 2015
- Full Text
- View/download PDF
24. Coloring a set of touching strings
- Author
-
Esperet, Louis, Gonçalves, Daniel, and Labourel, Arnaud
- Published
- 2009
- Full Text
- View/download PDF
25. On Universal Graphs of Minor Closed Families
- Author
-
Labourel, Arnaud
- Published
- 2008
- Full Text
- View/download PDF
26. Fault-Tolerant Rendezvous in Networks.
- Author
-
Chalopin, Jérémie, Dieudonné, Yoann, Labourel, Arnaud, and Pelc, Andrzej
- Published
- 2014
- Full Text
- View/download PDF
27. Short Labels by Traversal and Jumping
- Author
-
Bonichon, Nicolas, Gavoille, Cyril, and Labourel, Arnaud
- Published
- 2007
- Full Text
- View/download PDF
28. Collecting Information by Power-Aware Mobile Agents.
- Author
-
Anaya, Julian, Chalopin, Jérémie, Czyzowicz, Jurek, Labourel, Arnaud, Pelc, Andrzej, and Vaxès, Yann
- Published
- 2012
- Full Text
- View/download PDF
29. How to meet asynchronously (almost) everywhere.
- Author
-
Czyzowicz, Jurek, Labourel, Arnaud, and Pelc, Andrzej
- Published
- 2010
30. Asynchronous Deterministic Rendezvous in Bounded Terrains.
- Author
-
Czyzowicz, Jurek, Ilcinkas, David, Labourel, Arnaud, and Pelc, Andrzej
- Abstract
Two mobile agents (robots) have to meet in an a priori unknown bounded terrain modeled as a polygon, possibly with polygonal obstacles. Robots are modeled as points, and each of them is equipped with a compass. Compasses of robots may be incoherent. Robots construct their routes, but the actual walk of each robot is decided by the adversary that may, e.g., speed up or slow down the robot. We consider several scenarios, depending on three factors: (1) obstacles in the terrain are present, or not, (2) compasses of both robots agree, or not, (3) robots have or do not have a map of the terrain with their positions marked. The cost of a rendezvous algorithm is the worst-case sum of lengths of the robots΄ trajectories until their meeting. For each scenario we design a deterministic rendezvous algorithm and analyze its cost. We also prove lower bounds on the cost of any deterministic rendezvous algorithm in each case. For all scenarios these bounds are tight. [ABSTRACT FROM AUTHOR]
- Published
- 2010
- Full Text
- View/download PDF
31. Almost Optimal Asynchronous Rendezvous in Infinite Multidimensional Grids.
- Author
-
Bampas, Evangelos, Czyzowicz, Jurek, Gąsieniec, Leszek, Ilcinkas, David, and Labourel, Arnaud
- Abstract
Two anonymous mobile agents (robots) moving in an asynchronous manner have to meet in an infinite grid of dimension δ> 0, starting from two arbitrary positions at distance at most d. Since the problem is clearly infeasible in such general setting, we assume that the grid is embedded in a δ-dimensional Euclidean space and that each agent knows the Cartesian coordinates of its own initial position (but not the one of the other agent). We design an algorithm permitting the agents to meet after traversing a trajectory of length O(d
δ polylogd). This bound for the case of 2d -grids subsumes the main result of [12]. The algorithm is almost optimal, since the Ώ(dδ ) lower bound is straightforward. Further, we apply our rendezvous method to the following network design problem. The ports of the δ-dimensional grid have to be set such that two anonymous agents starting at distance at most d from each other will always meet, moving in an asynchronous manner, after traversing a O(dδ polylogd) length trajectory. We can also apply our method to a version of the geometric rendezvous problem. Two anonymous agents move asynchronously in the δ-dimensional Euclidean space. The agents have the radii of visibility of r1 and r2 , respectively. Each agent knows only its own initial position and its own radius of visibility. The agents meet when one agent is visible to the other one. We propose an algorithm designing the trajectory of each agent, so that they always meet after traveling a total distance of ]> , where r = min (r1 , r2 ) and for r ≥ 1. [ABSTRACT FROM AUTHOR]- Published
- 2010
- Full Text
- View/download PDF
32. Optimal Exploration of Terrains with Obstacles.
- Author
-
Czyzowicz, Jurek, Ilcinkas, David, Labourel, Arnaud, and Pelc, Andrzej
- Abstract
A mobile robot represented by a point moving in the plane has to explore an unknown flat terrain with impassable obstacles. Both the terrain and the obstacles are modeled as arbitrary polygons. We consider two scenarios: the unlimited vision, when the robot situated at a point p of the terrain explores (sees) all points q of the terrain for which the segment pq belongs to the terrain, and the limited vision, when we require additionally that the distance between p and q be at most 1. All points of the terrain (except obstacles) have to be explored and the performance of an exploration algorithm, called its complexity, is measured by the length of the trajectory of the robot. For unlimited vision we show an exploration algorithm with complexity ]> , where P is the total perimeter of the terrain (including perimeters of obstacles), D is the diameter of the convex hull of the terrain, and k is the number of obstacles. We do not assume knowledge of these parameters. We also prove a matching lower bound showing that the above complexity is optimal, even if the terrain is known to the robot. For limited vision we show exploration algorithms with complexity ]> , where A is the area of the terrain (excluding obstacles). Our algorithms work either for arbitrary terrains, if one of the parameters A or k is known, or for c-fat terrains, where c is any constant (unknown to the robot) and no additional knowledge is assumed. (A terrain ]> with obstacles is c-fat if R/r ≤ c, where R is the radius of the smallest disc containing ]> and r is the radius of the largest disc contained in ]> .) We also prove a matching lower bound ]> on the complexity of exploration for limited vision, even if the terrain is known to the robot. [ABSTRACT FROM AUTHOR]
- Published
- 2010
- Full Text
- View/download PDF
33. Optimality and Competitiveness of Exploring Polygons by Mobile Robots.
- Author
-
Czyzowicz, Jurek, Labourel, Arnaud, and Pelc, Andrzej
- Abstract
A mobile robot, represented by a point moving along a polygonal line in the plane, has to explore an unknown polygon and return to the starting point. The robot has a sensing area which can be a circle or a square centered at the robot. This area shifts while the robot moves inside the polygon, and at each point of its trajectory the robot ˵sees″ (explores) all points for which the segment between the robot and the point is contained in the polygon and in the sensing area. We focus on two tasks: exploring the entire polygon and exploring only its boundary. We consider several scenarios: both shapes of the sensing area and the Manhattan and the Euclidean metrics. We focus on two quality benchmarks for exploration performance: optimality (the length of the trajectory of the robot is equal to that of the optimal robot knowing the polygon) and competitiveness (the length of the trajectory of the robot is at most a constant multiple of that of the optimal robot knowing the polygon). Most of our results concern rectilinear polygons. We show that optimal exploration is possible in only one scenario, that of exploring the boundary by a robot with square sensing area, starting at the boundary and using the Manhattan metric. For this case we give an optimal exploration algorithm, and in all other scenarios we prove impossibility of optimal exploration. For competitiveness the situation is more optimistic: we show a competitive exploration algorithm for rectilinear polygons whenever the sensing area is a square, for both tasks, regardless of the metric and of the starting point. Finally, we show a competitive exploration algorithm for arbitrary convex polygons, for both shapes of the sensing area, regardless of the metric and of the starting point. [ABSTRACT FROM AUTHOR]
- Published
- 2009
- Full Text
- View/download PDF
34. Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs.
- Author
-
Hutchison, David, Kanade, Takeo, Kittler, Josef, Kleinberg, Jon M., Mattern, Friedemann, Mitchell, John C., Naor, Moni, Nierstrasz, Oscar, Pandu Rangan, C., Steffen, Bernhard, Sudan, Madhu, Terzopoulos, Demetri, Tygar, Doug, Vardi, Moshe Y., Weikum, Gerhard, Arge, Lars, Hoffmann, Michael, Welzl, Emo, Gavoille, Cyril, and Labourel, Arnaud
- Abstract
Implicit representation of graphs is a coding of the structure of graphs using distinct labels so that adjacency between any two vertices can be decided by inspecting their labels alone. All previous implicit representations of planar graphs were based on the classical three forests decomposition technique (a.k.a. Schnyder's trees), yielding asymptotically to a 3logn-bit label representation where n is the number of vertices of the graph. We propose a new implicit representation of planar graphs using asymptotically 2logn-bit labels. As a byproduct we have an explicit construction of a graph with n2 + o(1) vertices containing all n-vertex planar graphs as induced subgraph, the best previous size of such induced-universal graph was O(n3). More generally, for graphs excluding a fixed minor, we construct a 2logn + O(loglogn) implicit representation. For treewidth-k graphs we give a logn + O(kloglog(n/k)) implicit representation, improving the O(klogn) representation of Kannan, Naor and Rudich [18] (STOC '88). Our representations for planar and treewidth-k graphs are easy to implement, all the labels can be constructed in O(nlogn) time, and support constant time adjacency testing. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
35. Distributed Relationship Schemes for Trees.
- Author
-
Hutchison, David, Kanade, Takeo, Kittler, Josef, Kleinberg, Jon M., Mattern, Friedemann, Mitchell, John C., Naor, Moni, Nierstrasz, Oscar, Pandu Rangan, C., Steffen, Bernhard, Sudan, Madhu, Terzopoulos, Demetri, Tygar, Doug, Vardi, Moshe Y., Weikum, Gerhard, Tokuyama, Takeshi, Gavoille, Cyril, and Labourel, Arnaud
- Abstract
We consider a distributed representation scheme for trees, supporting some special relationships between nodes at small distance. For instance, we show that for a tree T and an integer k we can assign local information on nodes such that we can decide for any two nodes u and v if the distance between u and v is at most k and if so, compute it only using the local information assigned. For trees with n nodes, the local information assigned by our scheme are binary labels of logn + O(klog(klog(n/k))) bits, improving the results of Alstrup, Bille, and Rauhe (SODA '03). [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
36. Short Labels by Traversal and Jumping.
- Author
-
Flocchini, Paola, Gąsieniec, Leszek, Bonichon, Nicolas, Gavoille, Cyril, and Labourel, Arnaud
- Abstract
In this paper, we propose an efficient implicit representation of caterpillars and binary trees with n vertices. Our schemes, called Traversal & Jumping, assign to vertices of the tree distinct labels of log2n + O(1) bits, and support constant time adjacency queries between any two vertices by using only their labels. Moreover, all the labels can be constructed in O(n) time. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF
37. Edge Partition of Toroidal Graphs into Forests in Linear Time
- Author
-
Bonichon, Nicolas, Gavoille, Cyril, and Labourel, Arnaud
- Published
- 2005
- Full Text
- View/download PDF
38. How to Meet Asynchronously (Almost) Everywhere.
- Author
-
Czyzowicz, Jurek, Pelc, Andrzej, and Labourel, Arnaud
- Subjects
MOBILE agent systems ,ROBOTS ,GRAPH connectivity ,ALGORITHMS ,APPROXIMATION theory ,PATHS & cycles in graph theory ,INFINITY (Mathematics) - Abstract
Two mobile agents (robots) with distinct labels have to meet in an arbitrary, possibly infinite, unknown connected graph or in an unknown connected terrain in the plane. Agents are modeled as points, and the route of each of them only depends on its label and on the unknown environment. The actual walk of each agent also depends on an asynchronous adversary that may arbitrarily vary the speed of the agent, stop it, or even move it back and forth, as long as the walk of the agent is continuous, does not leave its route and covers all of it. Meeting in a graph means that both agents must be at the same time in some node or in some point inside an edge of the graph, while meeting in a terrain means that both agents must be at the same time in some point of the terrain. Does there exist a deterministic algorithm that allows any two agents to meet in any unknown environment in spite of this very powerful adversary? We give deterministic rendezvous algorithms for agents starting at arbitrary nodes of any anonymous connected graph (finite or infinite) and for agents starting at any interior points with rational coordinates in any closed region of the plane with path-connected interior. In the geometric scenario agents may have different compasses and different units of length. While our algorithms work in a very general setting - agents can, indeed, meet almost everywhere - we show that none of these few limitations imposed on the environment can be removed. On the other hand, our algorithm also guarantees the following approximate rendezvous for agents starting at arbitrary interior points of a terrain as previously stated agents will eventually get to within an arbitrarily small positive distance from each other. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
39. On local representation of distances in trees.
- Author
-
Gavoille, Cyril and Labourel, Arnaud
- Published
- 2007
- Full Text
- View/download PDF
40. Collaborative delivery on a fixed path with homogeneous energy-constrained agents.
- Author
-
Chalopin, Jérémie, Das, Shantanu, Disser, Yann, Labourel, Arnaud, and Mihalák, Matúš
- Subjects
- *
UNDIRECTED graphs , *DIRECTED graphs , *POLYNOMIAL time algorithms - Abstract
We consider the problem of collectively delivering a package from a specified source to a designated target location in a graph, using multiple mobile agents. Each agent starts from some vertex of the graph; it can move along the edges of the graph and can pick up the package from a vertex and drop it in another vertex during the course of its movement. However, each agent has limited energy budget allowing it to traverse a path of bounded length B ; thus, multiple agents need to collaborate to move the package to its destination. Given the positions of the agents in the graph and their energy budgets, the problem of finding a feasible movement schedule is called the Collaborative Delivery problem and has been studied before. One of the open questions from previous results is what happens when the delivery must follow a fixed path given in advance. Although this special constraint reduces the search space for feasible solutions, the problem remains NP hard, as the general version of the problem. We consider the optimization version of the problem that asks for the optimal energy budget B per agent which allows for a feasible delivery schedule along a fixed path, given the initial positions of the agents. We provide polynomial time approximation algorithms for both directed and undirected graphs, and establish hardness of approximation for the directed case. Note that the fixed path version of collaborative delivery requires completely different techniques since a single agent may be used multiple times, unlike the general version of collaborative delivery studied before. We show that restricting each agent to a single pickup allows better approximations for fixed path collaborative delivery compared to the original problem. Finally, we provide a polynomial time algorithm for determining a feasible delivery strategy, if any exists, for a given budget B when the number of available agents is bounded by a constant. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
41. Collaborative delivery with energy-constrained mobile robots.
- Author
-
Bärtschi, Andreas, Chalopin, Jérémie, Das, Shantanu, Disser, Yann, Geissmann, Barbara, Graf, Daniel, Labourel, Arnaud, and Mihalák, Matúš
- Subjects
- *
FREIGHT forwarders , *MOBILE robots , *NANOMEDICINE - Abstract
We consider the problem of collectively delivering some package from a specified source to a designated target location in a graph, using multiple mobile agents. Each agent has limited energy which constrains the distance it can move. Hence multiple agents need to collaborate to move the package, each agent handing over the package to the next agent to carry it forward. Given the positions of the agents in the graph and their respective budgets, the problem of finding a feasible movement schedule for the agents can be challenging. We consider two variants of the problem: in non-returning delivery, the agents can stop anywhere; whereas in returning delivery, each agent needs to return to its starting location, a variant which has not been studied before. We first provide a polynomial-time algorithm for returning delivery on trees, which is in contrast to the known (weak) NP-hardness of the non-returning version. In addition, we give resource-augmented algorithms for returning delivery in general graphs. Finally, we give tight lower bounds on the required resource augmentation for both variants of the problem. In this sense, our results close the gap left by previous research. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
42. Group search of the plane with faulty robots.
- Author
-
Czyzowicz, Jurek, Godon, Maxime, Kranakis, Evangelos, and Labourel, Arnaud
- Subjects
- *
ROBOTS , *AUTONOMOUS robots , *MOBILE robots , *COMMUNICATION models , *INFORMATION sharing , *WIRELESS communications - Abstract
A collection of k mobile robots, initially placed at the origin of the plane, are searching for a stationary target. Each robot r i has a unit visibility range and can move no faster than its maximal speed v i , for i = 1 , 2 ,... , k. The robots can communicate between themselves. We consider two communication models: wireless, in which a message sent by a robot can reach all other robots immediately, regardless of their positions, and face-to-face (F2F), in which robots can only exchange information when they are meeting. We assume that up to f robots, where f < k , may be unreliable. We consider two models of unreliability: (1) crash faults, in which we deal with an absence of some of the robots' capabilities (communication, perception, motion, etc.), and (2) byzantine faults, in which the robots may be malicious in that they may execute a wrong algorithm (e.g., transmitting wrong information). The goal is to minimize the group search time, which is equal to the time of arrival to the target of the last reliable robot. This is expressed as a function of d , the distance from the origin to the target. Our proposed algorithms for crash faults are asymptotically optimal in d in both communication models. For byzantine faults, our algorithm is asymptotically optimal for the wireless model. In the F2F model, we propose two algorithms: the first one has a competitive ratio of 2, while the second algorithm works for k ≥ 2 f + 2 and is optimal when the robots speeds are all equal. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
43. On asynchronous rendezvous in general graphs.
- Author
-
Bampas, Evangelos, Blin, Lélia, Czyzowicz, Jurek, Ilcinkas, David, Labourel, Arnaud, Potop-Butucaru, Maria, and Tixeuil, Sébastien
- Subjects
- *
GRAPH theory , *ASYNCHRONOUS learning , *POLYNOMIAL time algorithms , *COMPUTER algorithms , *MOBILE agent systems - Abstract
Abstract A pair of agents (robots) are moving in a graph with the goal of meeting at the same node or while traversing the same edge. An asynchronous adversary knows the prescribed walks of the two agents and is in complete control of the speed of each agent during its walk. We provide a complete characterization of pairs of walks that enforce rendezvous against an asynchronous adversary after traversing a given number of edges. The characterization is efficient in that it can be checked in polynomial time. We argue that the certificate of rendezvous enforcement that is produced by the checking algorithm contains a wealth of information on why rendezvous is enforced. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.