Search

Your search keyword '"Ilcinkas, David"' showing total 17 results
Start Over Author "Ilcinkas, David" Topic mobile agent
17 results on '"Ilcinkas, David"'

3. Exploration of Constantly Connected Dynamic Graphs Based on Cactuses

Author

Ilcinkas, David, Klasing, Ralf, Wade, Ahmed Mouhamadou, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, and Halldórsson, Magnús M., editor

Published
2014
Full Text
View/download PDF

4. Exploration of the T-Interval-Connected Dynamic Graphs: The Case of the Ring

Author

Ilcinkas, David, Wade, Ahmed Mouhamadou, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Moscibroda, Thomas, editor, and Rescigno, Adele A., editor

Published
2013
Full Text
View/download PDF

5. On the Power of Waiting When Exploring Public Transportation Systems

Author

Ilcinkas, David, Wade, Ahmed Mouhamadou, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Fernàndez Anta, Antonio, editor, Lipari, Giuseppe, editor, and Roy, Matthieu, editor

Published
2011
Full Text
View/download PDF

6. Asynchronous Deterministic Rendezvous in Bounded Terrains

Author

Czyzowicz, Jurek, Ilcinkas, David, Labourel, Arnaud, Pelc, Andrzej, 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, Patt-Shamir, Boaz, editor, and Ekim, Tınaz, editor

Published
2010
Full Text
View/download PDF

7. Space Lower Bounds for Graph Exploration via Reduced Automata

Author

Fraigniaud, Pierre, Ilcinkas, David, Rajsbaum, Sergio, Tixeuil, Sébastien, 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, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Pelc, Andrzej, editor, and Raynal, Michel, editor

Published
2005
Full Text
View/download PDF

9. Exploration of carrier-based time-varying networks: The power of waiting.

Author

Ilcinkas, David and Wade, Ahmed M.

Subjects
*TIME-varying networks, *PUBLIC transit, *PATIENCE, *GRAPH connectivity, *CARRIERS, *UNITS of time
Abstract

We study the problem of exploration by a mobile entity (agent) of a class of highly dynamic networks, namely the carrier graphs (the C-graphs, modeling public transportation systems, among others). These are defined by a set of carriers following infinitely their prescribed route along the stations of the network. Flocchini, Mans, and Santoro [9] studied this problem in the case when the agent must always travel on the carriers and thus cannot wait on a station. They described the necessary and sufficient conditions for the problem to be solvable and proved that the optimal worst-case number of time units (and thus of moves) to explore a n -node C-graph of k carriers and maximal period p is in Θ (k p 2) in the general case. In this paper, we study the impact of the ability to wait at the stations. We exhibit the necessary and sufficient conditions for the problem to be solvable in this context, and we prove that waiting at the stations allows the agent to reduce the optimal worst-case number of moves by a multiplicative factor of at least Θ (p) , while the worst-case time complexity is reduced to Θ (n p). (In any connected carrier graph, we have n ≤ k p.) We also show some complementary optimal results in specific cases (same period for all carriers, highly connected C-graphs). Finally this new ability allows the agent to completely map the C-graph, in addition to just exploring it. [ABSTRACT FROM AUTHOR]

Published
2020
Full Text
View/download PDF

10. Exploration of the <italic>T</italic>-Interval-Connected Dynamic Graphs: the Case of the Ring.

Author

Ilcinkas, David and Wade, Ahmed M.

Subjects
GRAPH connectivity, SPANNING trees, SUBGRAPHS, COMPUTATIONAL complexity, EDGES (Geometry)
Abstract

In this paper, we study the T-interval-connected dynamic graphs from the point of view of the time necessary and sufficient for their exploration by a mobile entity (agent). A dynamic graph (more precisely, an evolving graph) is T-interval-connected (T ≥ 1) if, for every window of T consecutive time steps, there exists a connected spanning subgraph that is stable (always present) during this period. This property of connection stability over time was introduced by Kuhn, Lynch and Oshman (Kuhn et al. 14) (STOC 2010). We focus on the case when the underlying graph is a ring of size n, and we show that the worst-case time complexity for the exploration problem is 2n − T − Θ(1) time units if the agent knows the dynamics of the graph, and n+nmax{1,T−1}(δ−1)±Θ(δ) time units otherwise, where δ is the maximum time between two successive appearances of an edge. [ABSTRACT FROM AUTHOR]

Published
2018
Full Text
View/download PDF

11. Locating a Target with an Agent Guided by Unreliable Local Advice

Author

Hanusse, Nicolas, Ilcinkas, David, Kosowski, Adrian, Nisse, Nicolas, 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), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, 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), Department of Algorithms and Systems Modelling [ETI GUT] (Gdansk University of Technology), Faculty of Electronics, Telecommunications and Informatics [GUT Gdańsk] (ETI), Gdańsk University of Technology (GUT)-Gdańsk University of Technology (GUT), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), See paper for details, ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-É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 (UB)-Inria Bordeaux - Sud-Ouest, Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)

Subjects
Random Walks, Faulty Networks, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Distributed Computing, Expanders, Mobile Agent
Abstract

International audience; We study the problem of finding a destination node t by a mobile agent in an unreliable network having the structure of an unweighted graph, in a model first proposed by Hanusse et al [20, 21]. Each node of the network is able to give advice concerning the next node to visit so as to go closer to the target t. Unfortunately, exactly k of the nodes, called liars, give advice which is incorrect. It is known that for an n-node graph G of maximum degree Δ ≥ 3, reaching a target at a distance of d from the initial location may require an expected time of 2^Ω(min{d,k}), for any d,k = O(log n), even when G is a tree. This paper focuses on strategies which efficiently solve the search problem in scenarios in which, at each node, the agent may only choose between following the local advice, or randomly selecting an incident edge. The strategy which we put forward, called R/A, makes use of a timer (step counter) to alternate between phases of ignoring advice (R) and following advice (A) for a certain number of steps. No knowledge of parameters n, d, or k is required, and the agent need not know by which edge it entered the node of its current location. The performance of this strategy is studied for two classes of regular graphs with extremal values of expansion, namely, for rings and for random Δ-regular graphs (an important class of expanders). For the ring, R/A is shown to achieve an expected searching time of 2d+k^Θ(1) for a worst-case distribution of liars, which is polynomial in both d and k. For random Δ-regular graphs, the expected searching time of the R/A strategy is O(k^3 log^3 n) a.a.s. The polylogarithmic factor with respect to n cannot be dropped from this bound; in fact, we show that a lower time bound of Ω(log n) steps holds for all d,k = Ω(log logn) in random Ω-regular graphs a.a.s. and applies even to strategies which make use of some knowledge of the environment. Finally, we study oblivious strategies which do not use any memory (in particular, with no timer). Such strategies are essentially a form of a random walk, possibly biased by local advice. We show that such biased random walks sometimes achieve drastically worse performance than the R/A strategy. In particular, on the ring, no biased random walk can have a searching time which is polynomial in d and k.

Published
2010

12. How to beat the random walk when you have a clock?

Author

Hanusse, Nicolas, Ilcinkas, David, Kosowski, Adrian, Nisse, Nicolas, 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), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, 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), Department of Algorithms and Systems Modelling [ETI GUT] (Gdansk University of Technology), Faculty of Electronics, Telecommunications and Informatics [GUT Gdańsk] (ETI), Gdańsk University of Technology (GUT)-Gdańsk University of Technology (GUT), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), INRIA, ANR-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009), Université de Bordeaux (UB)-É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 (UB)-Inria Bordeaux - Sud-Ouest, Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)

Subjects
Random Walks, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Faulty Networks, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Distributed Computing, Expanders, Mobile Agent
Abstract

We study the problem of finding a destination node $t$ by a mobile agent in an unreliable network having the structure of an unweighted graph, in a model first proposed by Hanusse {\it et al.}~\cite{HKK00,HKKK08}. Each node of the network is able to give advice concerning the next node to visit so as to go closer to the target $t$. Unfortunately, exactly $k$ of the nodes, called \emph{liars}, give advice which is incorrect. It is known that for an $n$-node graph $G$ of maximum degree $\Delta \geq 3$, reaching a target at a distance of $d$ from the initial location may require an expected time of $2^{\Omega(\min\{d,k\})}$, for any $d,k=O(\log n)$, even when $G$ is a tree. This paper focuses on strategies which efficiently solve the search problem in scenarios in which, at each node, the agent may only choose between following the local advice, or randomly selecting an incident edge. The strategy which we put forward, called \algo{R/A}, makes use of a timer (step counter) to alternate between phases of ignoring advice (\algo{R}) and following advice (\algo{A}) for a certain number of steps. No knowledge of parameters $n$, $d$, or $k$ is required, and the agent need not know by which edge it entered the node of its current location. The performance of this strategy is studied for two classes of regular graphs with extremal values of expansion, namely, for rings and for random $\maxdeg$-regular graphs (an important class of expanders). For the ring, \algo{R/A} is shown to achieve an expected searching time of $2d+k^{\Theta(1)}$ for a worst-case distribution of liars, which is polynomial in both $d$ and $k$. For random $\maxdeg$-regular graphs, the expected searching time of the \algo{R/A} strategy is $O(k^3 \log^3 n)$ a.a.s. The polylogarithmic factor with respect to $n$ cannot be dropped from this bound; in fact, we show that a lower time bound of $\Omega (\log n)$ steps holds for all $d,k=\Omega(\log\log n)$ in random $\maxdeg$-regular graphs a.a.s.\ and applies even to strategies which make use of some knowledge of the environment. Finally, we study oblivious strategies which do not use any memory (in particular, with no timer). Such strategies are essentially a form of a random walk, possibly biased by local advice. We show that such biased random walks sometimes achieve drastically worse performance than the \algo{R/A} strategy. In particular, on the ring, no biased random walk can have a searching time which is polynomial in $d$ and $k$

Published
2010

13. Asynchronous deterministic rendezvous in bounded terrains

Author

Czyzowicz, Jurek, Ilcinkas, David, Labourel, Arnaud, and Pelc, Andrzej

Subjects
*RELIEF models, *POLYGONS, *ROBOTS, *COMPASSES (Mathematical instruments), *COMPUTER algorithms, *COMPUTER simulation
Abstract

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 they meet. 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. [Copyright &y& Elsevier]

Published
2011
Full Text
View/download PDF

14. Remembering without memory: Tree exploration by asynchronous oblivious robots

Author

Flocchini, Paola, Ilcinkas, David, Pelc, Andrzej, and Santoro, Nicola

Subjects
*COMPUTER storage devices, *TREE graphs, *ASYNCHRONOUS circuits, *ROBOTS, *ALGORITHMS, *SWARM intelligence, *GRAPH labelings, *COMPUTATIONAL complexity
Abstract

Abstract: In an effort to understand the algorithmic limitations of computing by a swarm of robots, the research has focused on the minimal capabilities that allow a problem to be solved. The weakest of the commonly used models is Asynch where the autonomous mobile robots, endowed with visibility sensors (but otherwise unable to communicate), operate in Look-Compute-Move cycles performed asynchronously for each robot. The robots are often assumed (or required to be) oblivious: they keep no memory of observations and computations made in previous cycles. We consider the setting when the robots are dispersed in an anonymous and unlabeled graph, and they must perform the very basic task of exploration: within finite time every node must be visited by at least one robot and the robots must enter a quiescent state. The complexity measure of a solution is the number of robots used to perform the task. We study the case when the graph is an arbitrary tree and establish some unexpected results. We first prove that, in general, exploration cannot be done efficiently. More precisely we prove that there are -node trees where robots are necessary; this holds even if the maximum degree is . On the other hand, we show that if the maximum degree is , it is possible to explore with only robots. The proof of the result is constructive. We also prove that the size of the team used in our solution is asymptotically optimal: there are trees of degree , whose exploration requires robots. Our final result shows that the difficulty in tree exploration comes in fact from the symmetries of the tree. Indeed, we show that, in order to explore trees that do not have any non-trivial automorphisms, 4 robots are always sufficient and often necessary. [Copyright &y& Elsevier]

Published
2010
Full Text
View/download PDF

15. Impact of memory size on graph exploration capability

Author

Fraigniaud, Pierre, Ilcinkas, David, and Pelc, Andrzej

Subjects
*SEQUENTIAL machine theory, *MACHINE theory, *ROBOTS, *GRAPH theory
Abstract

Abstract: A mobile agent (robot), modeled as a finite automaton, has to visit all nodes of a regular graph. How does the memory size of the agent (the number of states of the automaton) influence its exploration capability? In particular, does every increase of the memory size enable an agent to explore more graphs? We give a partial answer to this problem by showing that a strict gain of the exploration power can be obtained by a polynomial increase of the number of states. We also show that, for automata with few states, the increase of memory by even one state results in the capability of exploring more graphs. [Copyright &y& Elsevier]

Published
2008
Full Text
View/download PDF

16. Graph exploration by a finite automaton

Author

Fraigniaud, Pierre, Ilcinkas, David, Peer, Guy, Pelc, Andrzej, and Peleg, David

Subjects
*SEQUENTIAL machine theory, *ROBOTICS, *COMPUTERS, *ROBOTS
Abstract

Abstract: A finite automaton, simply referred to as a robot, has to explore a graph whose nodes are unlabeled and whose edge ports are locally labeled at each node. The robot has no a priori knowledge of the topology of the graph or of its size. Its task is to traverse all the edges of the graph. We first show that, for any K-state robot and any , there exists a planar graph of maximum degree d with at most nodes that the robot cannot explore. This bound improves all previous bounds in the literature. More interestingly, we show that, in order to explore all graphs of diameter D and maximum degree d, a robot needs memory bits, even if we restrict the exploration to planar graphs. This latter bound is tight. Indeed, a simple DFS up to depth enables a robot to explore any graph of diameter D and maximum degree d using a memory of size bits. We thus prove that the worst case space complexity of graph exploration is bits. [Copyright &y& Elsevier]

Published
2005
Full Text
View/download PDF

17. Exploration of the T-Interval-Connected Dynamic Graphs: the Case of the Ring

Author

David Ilcinkas, Ahmed Mouhamadou Wade, 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), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, 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), Combinatoire et Algorithmique, Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), See paper for details., ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), Ilcinkas, David, BLANC - Calculabilité et complexité en distribué - - DISPLEXITY2011 - ANR-11-BS02-0014 - BLANC - VALID, Ecole polytechnique de Thiès, Ecole Polytechnique de Thiès, ANR-13-JS02-0002,MACARON,Bouger et Calculer: Agents, Robots et Réseaux(2013), Université de Bordeaux (UB)-É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 (UB)-Inria Bordeaux - Sud-Ouest, and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, Exploration problem, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Stability (probability), Theoretical Computer Science, Combinatorics, 0202 electrical engineering, electronic engineering, information engineering, Connection (algebraic framework), Time complexity, Mathematics, Dynamic graphs, Discrete mathematics, Mobile agent, Ring (mathematics), Unit of time, 020206 networking & telecommunications, T-interval-connectivity, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Computational Theory and Mathematics, 010201 computation theory & mathematics, Theory of computation, Interval (graph theory), 020201 artificial intelligence & image processing, Exploration, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Focus (optics)
Abstract

In this paper, we study the T-interval-connected dynamic graphs from the point of view of the time necessary and sufficient for their exploration by a mobile entity (agent). A dynamic graph (more precisely, an evolving graph) is T-interval-connected (T ≥ 1) if, for every window of T consecutive time steps, there exists a connected spanning subgraph that is stable (always present) during this period. This property of connection stability over time was introduced by Kuhn, Lynch and Oshman (Kuhn et al. 14) (STOC 2010). We focus on the case when the underlying graph is a ring of size n, and we show that the worst-case time complexity for the exploration problem is 2n − T − Θ(1) time units if the agent knows the dynamics of the graph, and $n+ \frac {n}{\max \{1, T-1\} } (\delta -1) \pm {\Theta }(\delta )$ time units otherwise, where δ is the maximum time between two successive appearances of an edge.

Published
2013

Catalog

Books, media, physical & digital resources
See catalog results