Abstract
We study the problem of exploration by a mobile entity (agent) of a class of dynamic networks, namely constantly connected dynamic graphs. This problem has already been studied in the case where the agent knows the dynamics of the graph and the underlying graph is a ring of n vertices [5]. In this paper, we consider the same problem and we suppose that the underlying graph is a cactus graph (a connected graph in which any two simple cycles have at most one vertex in common). We propose an algorithm that allows the agent to explore these dynamic graphs in at most \(2^{O(\sqrt{\log n})} n\) time units. We show that the lower bound of the algorithm is \(2^{\Omega(\sqrt{\log n})} n\) time units.
Partially supported by the ANR project DISPLEXITY (ANR-11-BS02-014). This study has been carried out in the frame of “the Investments for the future” Programme IdEx Bordeaux – CPU (ANR-10-IDEX-03-02).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Burkard, R., Krarup, J.: A Linear Algorithm for the Pos/Neg-Weighted 1-Median Problem on a Cactus. Computing 60(3), 193–216 (1998)
Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems 27(5) (2012)
Dutta, C., Pandurangan, G., Rajaraman, R., Sun, Z.: Information spreading in dynamic networks. CoRR, abs/1112.0384 (2011)
Ferreira, A.: Building a Reference Combinatorial Model for Dynamic Networks: Initial Results in Evolving Graphs. INRIA, RR-5041 (2003)
Ilcinkas, D., Wade, A.M.: Exploration of the T-Interval-Connected Dynamic Graphs: The Case of the Ring. In: Moscibroda, T., Rescigno, A.A. (eds.) SIROCCO 2013. LNCS, vol. 8179, pp. 13–23. Springer, Heidelberg (2013)
Kuhn, F., Lynch, N.A., Oshman, R.: Distributed computation in dynamic networks. In: 42nd ACM Symposium on Theory of Computing (STOC), pp. 513–522 (2010)
Kuhn, F., Oshman, R.: Dynamic networks: models and algorithms. ACM SIGACT News 42(1), 82–96 (2011)
Mömke, T., Svensson, O.: Approximating Graphic TSP by Matchings. In: 52nd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 560–569 (2011)
Mucha, M.: 13/9-approximation for Graphic TSP. In: 29th Int. Symposium on Theoretical Aspects of Computer Science (STACS), pp. 30–41 (2012)
O’Dell, R., Wattenhofer, R.: Information dissemination in highly dynamic graphs. In: DIALM-POMC, pp. 104–110 (2005)
Sebö, A., Vygen, J.: Shorter Tours by Nicer Ears: 7/5-approximation for graphic TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. Combinatorica (to appear)
Shannon, C.E.: Presentation of a maze-solving machine. In: 8th Conf. of the Josiah Macy Jr. Found (Cybernetics), pp. 173–180 (1951)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Ilcinkas, D., Klasing, R., Wade, A.M. (2014). Exploration of Constantly Connected Dynamic Graphs Based on Cactuses. In: Halldórsson, M.M. (eds) Structural Information and Communication Complexity. SIROCCO 2014. Lecture Notes in Computer Science, vol 8576. Springer, Cham. https://doi.org/10.1007/978-3-319-09620-9_20
Download citation
DOI: https://doi.org/10.1007/978-3-319-09620-9_20
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-09619-3
Online ISBN: 978-3-319-09620-9
eBook Packages: Computer ScienceComputer Science (R0)