Search

Showing total 17 results
Start Over Search Limiters Full Text Topic combinatorics
17 results

1. Enclosings of decompositions of complete multigraphs in 2-edge-connected r -factorizations

Author

John Asplund, Pierre Charbit, Carl Feghali, Dalton State College, University System of Georgia (USG), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), 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 de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), University of Bergen (UIB), This paper received partial support his paper received partial support by Fondation Sciences Mathématiques de Paris and the Research Council of Norway via the project CLASSIS, Grant Number 249994., and University of Bergen (UiB)

Subjects
Discrete mathematics, 010102 general mathematics, Multigraph, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Theoretical Computer Science, Combinatorics, Factorization, 010201 computation theory & mathematics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Discrete Mathematics and Combinatorics, Partition (number theory), Mathematics - Combinatorics, Combinatorics (math.CO), 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics, 05B99
Abstract

A decomposition of a multigraph $G$ is a partition of its edges into subgraphs $G(1), \ldots , G(k)$. It is called an $r$-factorization if every $G(i)$ is $r$-regular and spanning. If $G$ is a subgraph of $H$, a decomposition of $G$ is said to be enclosed in a decomposition of $H$ if, for every $1 \leq i \leq k$, $G(i)$ is a subgraph of $H(i)$. Feghali and Johnson gave necessary and sufficient conditions for a given decomposition of $\lambda K_n$ to be enclosed in some $2$-edge-connected $r$-factorization of $\mu K_{m}$ for some range of values for the parameters $n$, $m$, $\lambda$, $\mu$, $r$: $r=2$, $\mu>\lambda$ and either $m \geq 2n-1$, or $m=2n-2$ and $\mu = 2$ and $\lambda=1$, or $n=3$ and $m=4$. We generalize their result to every $r \geq 2$ and $m \geq 2n - 2$. We also give some sufficient conditions for enclosing a given decomposition of $\lambda K_n$ in some $2$-edge-connected $r$-factorization of $\mu K_{m}$ for every $r \geq 3$ and $m = (2 - C)n$, where $C$ is a constant that depends only on $r$, $\lambda$ and~$\mu$., Comment: 17 pages; fixed the proof of Theorem 1.4 and other minor changes

Published
2019

2. Towards a symplectic version of the Chevalley restriction theorem

Author

Ronan Terpereau, Manfred Lehn, Christian Lehn, Michael Bulois, Algèbre, géométrie, logique ( AGL ), Institut Camille Jordan [Villeurbanne] ( ICJ ), École Centrale de Lyon ( ECL ), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 ( UCBL ), Université de Lyon-Institut National des Sciences Appliquées de Lyon ( INSA Lyon ), Université de Lyon-Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Jean Monnet [Saint-Étienne] ( UJM ) -Centre National de la Recherche Scientifique ( CNRS ) -École Centrale de Lyon ( ECL ), Université de Lyon-Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Jean Monnet [Saint-Étienne] ( UJM ) -Centre National de la Recherche Scientifique ( CNRS ), Fakultät für Mathematik der Technischen Universität Chemnitz, Fakultaet fuer Mathematik der Technischen Universitaet Chemnitz, Institut für Mathematik ( MI ), Johannes Gutenberg - Universität Mainz ( JGU ), Institut de Mathématiques de Bourgogne [Dijon] ( IMB ), Université de Bourgogne ( UB ) -Centre National de la Recherche Scientifique ( CNRS ), Max Planck Institute for Mathematics ( Bonn ), The second-named author gratefully acknowledges the support by the DFG through the research grant Le 3093/2-1. The thirdnamed author is supported by the SFB Transregio 45 'Periods, Moduli Spaces and Arithmetic of Algebraic Varieties'. The fourth-named author is grateful to the Max-Planck-Institut für Mathematik of Bonn for the warm hospitality and support provided during the writing of this paper. Part ofthe genesis of this paper occurred during the half semester Algebraic Groups and Representations supported by the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program 'Investissements d'Avenir' (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR)., ANR-11-IDEX-0007-02/10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon ( 2011 ), ANR-15-CE40-0012,GeoLie,GeoLie, Algèbre, géométrie, logique (AGL), Institut Camille Jordan [Villeurbanne] (ICJ), École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet [Saint-Étienne] (UJM)-Centre National de la Recherche Scientifique (CNRS)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet [Saint-Étienne] (UJM)-Centre National de la Recherche Scientifique (CNRS), Chemnitz University of Technology / Technische Universität Chemnitz, Institut für Mathematik (MI), Johannes Gutenberg - Universität Mainz (JGU), Institut de Mathématiques de Bourgogne [Dijon] (IMB), Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université de Bourgogne (UB), Max Planck Institute for Mathematics (MPIM), Max-Planck-Gesellschaft, ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), and ANR-15-CE40-0012,GéoLie,Méthodes géométriques en théorie de Lie(2015)

Subjects
Polar representation, Symplectic variety, [ MATH.MATH-SG ] Mathematics [math]/Symplectic Geometry [math.SG], 01 natural sciences, Combinatorics, Mathematics - Algebraic Geometry, symbols.namesake, Morphism, 0103 physical sciences, FOS: Mathematics, 14L30, 53D20, 20G05, 20G20, 13A50, Representation Theory (math.RT), 0101 mathematics, MSC: 14L30, 53D20, 20G05, 20G20, 13A50, Mathematics::Representation Theory, Symplectic reduction, Algebraic Geometry (math.AG), Moment map, Mathematics, Weyl group, Algebra and Number Theory, Conjecture, [MATH.MATH-RT]Mathematics [math]/Representation Theory [math.RT], Reductive group, 010102 general mathematics, [MATH.MATH-SG]Mathematics [math]/Symplectic Geometry [math.SG], [ MATH.MATH-RT ] Mathematics [math]/Representation Theory [math.RT], [ MATH.MATH-AG ] Mathematics [math]/Algebraic Geometry [math.AG], Mathematics - Symplectic Geometry, symbols, Symplectic Geometry (math.SG), 010307 mathematical physics, Isomorphism, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], Mathematics - Representation Theory, Symplectic geometry
Abstract

If $(G,V)$ is a polar representation with Cartan subspace $\mathfrak c$ and Weyl group $W$, it is shown that there is a natural morphism of Poisson schemes $\mathfrak c \oplus {\mathfrak c}^*/W \to V\oplus V^*/\!\!/\!\!/ G$. This morphism is conjectured to be an isomorphism of the underlying reduced varieties if $(G,V)$ is visible. The conjecture is proved for visible stable locally free polar representations and certain further examples., Comment: 18 pages, final version

Published
2017

3. More efficient periodic traversal in anonymous undirected graphs

Author

Kunihiko Sadakane, Ioannis Lignos, Leszek Gsieniec, Ralf Klasing, Jesper Jansson, Stefan Dobrev, Russell Martin, David Ilcinkas, Wing-Kin Sung, Jurek Czyzowicz, Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), Institute of Mathematics, Slovak Academy of Science [Bratislava] (SAS), Department of Computer Science [Liverpool], University of Liverpool, 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), Ochanomizu University, Department of Computer Science, Durham University, Principles of Informatics Research Division, National Institute of Informatics (NII), National University of Singapore (NUS), See paper for details, ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), INRIA Futurs, See paper for details., ANR-05-MMSA-0006,ALPAGE,ALgorithmique des Plates-formes A Grande Echelle(2005), 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
FOS: Computer and information sciences, General Computer Science, Discrete Mathematics (cs.DM), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Comparability graph, Constant-memory agent, 0102 computer and information sciences, 02 engineering and technology, Strength of a graph, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Upper and lower bounds, law.invention, Theoretical Computer Science, Combinatorics, Graph exploration, law, Graph power, Line graph, Graph traversal, 0202 electrical engineering, electronic engineering, information engineering, Algorithms and data structures, Oblivious agent, Undirected graph, Mathematics, Discrete mathematics, Mobile entity, Voltage graph, Three-layer partition, Butterfly graph, Periodic graph traversal, Tree traversal, 010201 computation theory & mathematics, 020201 artificial intelligence & image processing, Periodic graph (geometry), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Null graph, Span tree, Period length, Computer Science - Discrete Mathematics, Computer Science(all)
Abstract

International audience; We consider the problem of periodic graph exploration in which a mobile entity with constant memory, an agent, has to visit all n nodes of an input simple, connected, undirected graph in a periodic manner. Graphs are assumed to be anonymous, that is, nodes are unlabeled. While visiting a node, the agent may distinguish between the edges incident to it; for each node v, the endpoints of the edges incident to v are uniquely identified by different integer labels called port numbers. We are interested in algorithms for assigning the port numbers together with traversal algorithms for agents using these port numbers to obtain short traversal periods. Periodic graph exploration is unsolvable if the port numbers are set arbitrarily; see Budach (1978) [1]. However, surprisingly small periods can be achieved by carefully assigning the port numbers. Dobrev et al. (2005) [4] described an algorithm for assigning port numbers and an oblivious agent (i.e., an agent with no memory) using it, such that the agent explores any graph with n nodes within the period 10n. When the agent has access to a constant number of memory bits, the optimal length of the period was proved in Gąsieniec et al. (2008) [7] to be no more than 3.75n−2 (using a different assignment of the port numbers and a different traversal algorithm). In this paper, we improve both these bounds. More precisely, we show how to achieve a period length of at most for oblivious agents and a period length of at most 3.5n−2 for agents with constant memory. To obtain our results, we introduce a new, fast graph decomposition technique called a three-layer partition that may also be useful for solving other graph problems in the future. Finally, we present the first non-trivial lower bound, 2.8n−2, on the period length for the oblivious case.

Published
2012

4. Convergence regions for the Chebyshev–Halley family

Author

B. Campos, Jordi Canela, P. Vindel, and The authors would like to thank the anonymous referees for their suggestions and comments, which improved this paper. The first and third authors were supported by the Spanish project MTM2014-52016-C02-2-P, the Generalitat Valenciana Project PROMETEO/2016/089 and UJI project P1.1B20115-16. The second author was supported by RedIUM and MINECO (Spain) through the research network MTM2014-55580-REDT and by the mathematics institute IMAC (Castellon, Spain).

Subjects
roots, Numerical Analysis, Pure mathematics, Chebyshev–Halley family, Iterative method, polynomials, Applied Mathematics, Chebyshev systems, 010102 general mathematics, 010103 numerical & computational mathematics, dynamics, Parameter space, Fixed point, 01 natural sciences, Attraction, Chebyshev filter, Critical point (mathematics), Combinatorics, Quadratic equation, Modeling and Simulation, Polinomis, 0101 mathematics, Sistemes de Chebyshev, Mathematics
Abstract

In this paper we study the dynamical behavior of the Chebyshev–Halley methods on the family of degree n polynomials z n + c . We prove that, despite increasing the degree, it is still possible to draw the parameter space by using the orbit of a single critical point. For the methods having z = ∞ as an attracting fixed point, we show how the basins of attraction of the roots become smaller as the value of n grows. We also demonstrate that, although the convergence order of the Chebyshev–Halley family is 3, there is a member of order 4 for each value of n. In the case of quadratic polynomials, we bound the set of parameters which correspond to iterative methods with stable behaviour other than the basins of attraction of the roots.

Published
2018

5. Various approaches for the study of the complexity of some families of pseudorandom subsets

Author

Domingo Gómez-Pérez, Cécile Dartyge, Institut Élie Cartan de Lorraine (IECL), Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Universidad de Cantabria [Santander], During the preparation of this paper the second author was par-tially supported by project MTM2014-55421-P from the Ministerio de Economia y Competitividad, and ANR-14-CE34-0009,MuDeRa,Multiplicativity, determinism, and Randomness(2014)

Subjects
Discrete mathematics, Pseudorandom number generator, Combinatorics, Development (topology), Geometry of numbers, General Mathematics, Discrete geometry, Pseudorandomness, complexity, Randomness, [MATH.MATH-NT]Mathematics [math]/Number Theory [math.NT], Mathematics
Abstract

International audience; Studying randomness in different structures is important from the development of applications and theory. Dartyge, Mosaki and Sárközy (among others) have studied measures of randomness for families of subsets of integers. In this article, we improve results on the complexity of some families defined by polynomials, introducing new techniques from areas such us combinatorial geometry, geometry of numbers and additive combinatorics.

Published
2017

6. Derandomizing random walks in undirected graphs using locally fair exploration strategies

Author

Ralf Klasing, Adrian Kosowski, Colin Cooper, David Ilcinkas, Department of Computer Science (DCS), King‘s College London, 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, 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)-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-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), 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), ANR-05-MMSA-0006,ALPAGE,ALgorithmique des Plates-formes A Grande Echelle(2005), Université Sciences et Technologies - Bordeaux 1 (UB)-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)-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é de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Mathematical optimization, Computer Networks and Communications, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Comparability graph, Random walk, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, law.invention, Theoretical Computer Science, Combinatorics, Indifference graph, Graph exploration, law, Graph power, Line graph, Random regular graph, 0202 electrical engineering, electronic engineering, information engineering, Pancyclic graph, Mathematics, Discrete mathematics, Block graph, graph exploration : Propp machine, Directed graph, Feedback arc set, Computational Theory and Mathematics, 010201 computation theory & mathematics, Hardware and Architecture, Robbins' theorem, Graph (abstract data type), 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

International audience; We consider the problem of exploring an anonymous undirected graph using an oblivious robot. The studied exploration strategies are designed so that the next edge in the robot's walk is chosen using only local information, and so that some local equity (fairness) criterion is satisfied for the adjacent undirected edges. Such strategies can be seen as an attempt to derandomize random walks, and are natural counterparts for undirected graphs of the rotor-router model for symmetric directed graphs. The first of the studied strategies, known as Oldest-First (OF), always chooses the neighboring edge for which the most time has elapsed since its last traversal. Unlike in the case of symmetric directed graphs, we show that such a strategy in some cases leads to exponential cover time. We then consider another strategy called Least-Used-First (LUF) which always uses adjacent edges which have been traversed the smallest number of times. We show that any Least-Used-First exploration covers a graph G=(V,E) of diameter diam within time O(diam|E|), and in the long run traverses all edges of G with the same frequency.

Published
2011

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

Author

Nicola Santoro, David Ilcinkas, Andrzej Pelc, Paola Flocchini, Distributed Computing Research Group [Ottawa], University of Ottawa [Ottawa], 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), Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), School of Computer Science [Ottawa], Carleton University, 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, Partially supported by NSERC Discovery grant. Andrzej Pelc is also partially supported by the Research Chair in Distributed Computing at the Université du Québec en Outaouais. This work was done during the stay of David Ilcinkas at the Research Chair in Distributed Computing of the Université du Québec en Outaouais and at the University of Ottawa, as a postdoctoral fellow., and Alexander A. Shvartsman, Pascal Felber

Subjects
Theoretical computer science, General Computer Science, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, exploration, 01 natural sciences, Constructive, Theoretical Computer Science, Combinatorics, Computer Science::Robotics, oblivious, mobile agent, 0202 electrical engineering, electronic engineering, information engineering, Mathematics, asynchronous, Discrete mathematics, Degree (graph theory), Swarm behaviour, robot, Mobile robot, Binary logarithm, tree, Asymptotically optimal algorithm, 010201 computation theory & mathematics, Asynchronous communication, Robot, Graph (abstract data type), 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Computer Science(all)
Abstract

International audience; In the 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 {\sc 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 {\em 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 $n$-node trees where $\Omega(n)$ robots are necessary; this holds even if the maximum degree is $4$. On the other hand, we show that if the maximum degree is $3$, it is possible to explore with only $O(\frac{\log n} {\log\log n})$ robots. The proof of the result is constructive. We also prove that the size of the team used in our solution is asymptotically {\em optimal}: there are trees of degree $3$, whose exploration requires $\Omega(\frac{\log n}{\log\log n})$ 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.

Published
2010

8. Beachcombing on Strips and Islands

Author

Evangelos Bampas, David Ilcinkas, Jurek Czyzowicz, Ralf Klasing, Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), 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), ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), ANR-10-IDEX-0003,IDEX BORDEAUX,Initiative d'excellence de l'Université de Bordeaux(2010), See paper for details., and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Discrete mathematics, Conjecture, General Computer Science, Competitive analysis, Computer science, Generalization, Approximation algorithm, Mobile robot, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Infimum and supremum, Domain (mathematical analysis), Theoretical Computer Science, Preferred walking speed, Combinatorics, 010201 computation theory & mathematics, Line (geometry), 0202 electrical engineering, electronic engineering, information engineering, Robot, Point (geometry), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Online algorithm, Mathematics
Abstract

International audience; A group of mobile robots (beachcombers) have to search collectively every point of a given domain. At any given moment, each robot can be in {\em walking mode} or in {\em searching mode}. It is assumed that each robot's maximum allowed searching speed is strictly smaller than its maximum allowed walking speed. A point of the domain is searched if at least one of the robots visits it in searching mode. The Beachcombers' Problem consists in developing efficient {\em schedules} (algorithms) for the robots which collectively search all the points of the given domain as fast as possible. We consider searching schedules in the following one-dimensional geometric domains: the cycle of a known circumference $L$, the finite straight line segment of a known length $L$, and the semi-infinite line $[0,+\infty)$.We first consider the {\em online} Beachcombers' Problem (i.e.~the scenario when the robots do not know in advance the length of the segment to be searched), where the robots are initially collocated at the origin of a semi-infinite line. It is sought to design a schedule $A$ with maximum {\em speed} $S$, defined as $S = \inf_{\ell}{\frac{\ell}{t_A(\ell)}}$, where $t_A(\ell)$ denotes the time when the search of the segment $[0,\ell]$ is completed under $A$. We consider a {\em discrete} and a {\em continuous} version of the problem, depending on whether the infimum is takenover $\ell \in \mathbb{N}^*$ or $\ell \geq 1$. We prove that the $\mathtt{LeapFrog}$ algorithm, which was proposed in [Czyzowicz et al., SIROCCO 2014, LNCS 8576, pp. 23--36 (2014)], is in fact optimal in the discrete case. This settles in the affirmative a conjecture from that paper. We also show how to extend this result to the more general continuous online setting.For the {\em offline} version of the Beachcombers' Problem (i.e.~the scenario when the robots know in advance the length of the segment to be searched), we consider the \emph{$t$-source} Beachcombers' Problem (i.e.~all robots start from a fixed number $t \geq 1$ of starting positions) on the cycle and on the finite segment. For the \emph{$t$-source} Beachcombers' Problem on the cycle, we show that the structure of the optimal solutions is identical to the structure of the optimal solutions to the $2t$-source Beachcombers' Problem on a finite segment. In consequence, by using results from [Czyzowicz et al., ALGOSENSORS 2014, LNCS 8847, pp.~3--21 (2014)], we prove that the \emph{1-source} Beachcombers' Problem on the cycle is NP-hard, and we derive approximation algorithms for the problem. For the \emph{$t$-source} variant of the Beachcombers' Problem on the cycle and on the finite segment, we also derive efficient approximation algorithms.One important contribution of our work is that, in all variants of the offline Beachcombers' Problem that we discuss, we allow the robots to \emph{change direction of movement} and search points of the domain on both sides of their respective starting positions. This represents a significant generalization compared to the model considered in~[Czyzowicz et al., ALGOSENSORS 2014, LNCS 8847, pp. 3--21 (2014)], in which each robot had a fixed direction of movement that was specified as part of the solution to the problem. We manage to prove that changes of direction do not help the robots achieve optimality.

Published
2015

9. Exploration of Constantly Connected Dynamic Graphs Based on Cactuses

Author

Ahmed Mouhamadou Wade, David Ilcinkas, Ralf Klasing, 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), See papers for details., and ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011)

Subjects
Mobile agent, Block graph, Discrete mathematics, Symmetric graph, Cactus graph, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, law.invention, Combinatorics, Connectivity over time, 010201 computation theory & mathematics, law, Random regular graph, Clique-width, Line graph, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Exploration, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Pancyclic graph, Dynamic graphs, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics, Distance-hereditary graph
Abstract

International audience; 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 \cite{IW13}. 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.

Published
2014

10. On the Communication Complexity of Distributed Name-Independent Routing Schemes

Author

Nicolas Hanusse, Christian Glacet, David Ilcinkas, Cyril Gavoille, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-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), See paper for details., ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), European Project: 258307,EC:FP7:ICT,FP7-ICT-2009-5,EULER(2010), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Ilcinkas, David, BLANC - Calculabilité et complexité en distribué - - DISPLEXITY2011 - ANR-11-BS02-0014 - BLANC - VALID, and Experimental UpdateLess Evolutive Routing - EULER - - EC:FP7:ICT2010-10-01 - 2014-06-30 - 258307 - VALID

Subjects
TheoryofComputation_MISCELLANEOUS, distributed routing algorithm, compact routing, Routing table, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 020206 networking & telecommunications, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, bounded stretch, 01 natural sciences, Combinatorics, Asynchronous algorithms, 010201 computation theory & mathematics, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, Shortest path problem, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Graph (abstract data type), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Communication complexity, name-independent, Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

International audience; We present a distributed asynchronous algorithm that, for every undirected weighted $n$-node graph $G$, constructs name-independent routing tables for $G$. The size of each table is $\tO(\sqrt{n}\,)$, whereas the length of any route is stretched by a factor of at most~$7$ w.r.t. the shortest path. At any step, the memory space of each node is $\tO(\sqrt{n}\,)$. The algorithm terminates in time $O(D)$, where $D$ is the hop-diameter of $G$. In synchronous scenarios and with uniform weights, it consumes $\tO(m\sqrt{n} + n^{3/2}\min\set{D,\sqrt{n}\,})$ messages, where $m$ is the number of edges of $G$. In the realistic case of sparse networks of poly-logarithmic diameter, the communication complexity of our scheme, that is $\tO(n^{3/2})$, improves by a factor of $\sqrt{n}$ the communication complexity of \emph{any} shortest-path routing scheme on the same family of networks. This factor is provable thanks to a new lower bound of independent interest.

Published
2013

11. 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

12. The Impact of Edge Deletions on the Number of Errors in Networks

Author

Christian Glacet, Nicolas Hanusse, David Ilcinkas, 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), 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), 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-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université Sciences et Technologies - Bordeaux 1 (UB)-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é 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
Computer science, dynamic graph, Mathematics::History and Overview, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 010501 environmental sciences, Expected value, Network topology, 01 natural sciences, Graph, Combinatorics, shortest path and routing, Mathematics::Logic, 010201 computation theory & mathematics, Algorithm, 0105 earth and related environmental sciences, errors and faults
Abstract

In this paper, we deal with an error model in distributed networks. For a target t, every node is assumed to give an advice, ie. to point to a neighbour that take closer to the destination. Any node giving a bad advice is called a liar. Starting from a situation without any liar, we study the impact of topology changes on the number of liars. More precisely, we establish a relationship between the number of liars and the number of distance changes after one edge deletion. Whenever l deleted edges are chosen uniformly at random, for any graph with n nodes, m edges and diameter D, we prove that the expected number of liars and distance changes is $O(\frac{\ell^2Dn}{m})$ in the resulting graph. The result is tight for l=1. For some specific topologies, we give more precise bounds.

Published
2011

13. Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces

Author

David Ilcinkas, Nicolas Hanusse, Nicolas Bonichon, Cyril Gavoille, Gavoille, Cyril, 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), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), 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), and Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest

Subjects
spanner, 0102 computer and information sciences, Delaunay triangulation, Computer Science::Computational Geometry, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, law.invention, Combinatorics, symbols.namesake, law, Line graph, 0101 mathematics, Beta skeleton, Mathematics, Forbidden graph characterization, Block graph, orthogonal surface, 010102 general mathematics, theta-graph, 1-planar graph, Geometric graph theory, Planar graph, realizability, [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], 010201 computation theory & mathematics, symbols, Topological graph theory
Abstract

International audience; $\Theta_k$-graphs are geometric graphs that appear in the context of graph navigation. The shortest-path metric of these graphs is known to approximate the Euclidean complete graph up to a factor depending on the cone number $k$ and the dimension of the space. TD-Delaunay graphs, a.k.a.~triangular-distance Delaunay triangulations, introduced by Chew, have been shown to be plane $2$-spanners of the 2D Euclidean complete graph, i.e., the distance in the TD-Delaunay graph between any two points is no more than twice the distance in the plane. Orthogonal surfaces are geometric objects defined from independent sets of points of the Euclidean space. Orthogonal surfaces are well studied in combinatorics (orders, integer programming) and in algebra. From orthogonal surfaces, geometric graphs, called geodesic embeddings can be built. In this paper, we introduce a specific subgraph of the $\TG$-graph defined in the 2D Euclidean space, namely the $\DTG$-graph, composed of the even-cone edges of the $\TG$-graph. Our main contribution is to show that these graphs are exactly the TD-Delaunay graphs, and are strongly connected to the geodesic embeddings of orthogonal surfaces of coplanar points in the 3D Euclidean space. Using these new bridges between these three fields, we establish: \begin{itemize} \item Every $\TG$-graph is the union of two spanning TD-Delaunay graphs. In particular, $\TG$-graphs are $2$-spanners of the Euclidean graph, and the bound of~$2$ on the stretch factor is the best possible. It was not known that $\Theta_6$-graphs are $t$-spanners for some constant $t$, and $\Theta_7$-graphs were only known to be $t$-spanners for $t \approx 7.562$. \item Every plane triangulation is TD-Delaunay realizable, i.e., every combinatorial plane graph for which all its interior faces are triangles is the TD-Delaunay graph of some point set in the plane. Such realizability property does not hold for classical Delaunay triangulations. \end{itemize}

Published
2010

14. Euler Tour Lock-In Problem in the Rotor-Router Model

Author

Adrian Kosowski, Ralf Klasing, Evangelos Bampas, David Ilcinkas, Leszek Gąsieniec, Nicolas Hanusse, School of of Electrical and Computer Engineering [Athens] (School of E.C.E), National Technical University of Athens [Athens] (NTUA), 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 Computer Science [Liverpool], University of Liverpool, 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), 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), See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), 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)

Subjects
Router, 010102 general mathematics, Eulerian path, Topology (electrical circuits), 0102 computer and information sciences, Random walk, 01 natural sciences, Complete bipartite graph, Numbering, Combinatorics, symbols.namesake, 010201 computation theory & mathematics, Bounded function, symbols, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], 0101 mathematics, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics, Rotor (mathematics)
Abstract

International audience; The rotor-router model, also called the Propp machine, was first considered as a deterministic alternative to the random walk. It is known that the route in an undirected graph G=(V,E), where |V|=n and |E|=m, adopted by an agent controlled by the rotor-router mechanism forms eventually an Euler tour based on arcs obtained via replacing each edge in G by two arcs with opposite direction. The process of ushering the agent to an Euler tour is referred to as the lock-in problem. In recent work [Yan03] Yanovski et al. proved that independently of the initial configuration of the rotor-router mechanism in G the agent locks-in in time bounded by 2m diam, where diam is the diameter of G. This upper bound can be matched asymptotically in lollipop graphs. In this paper we examine the dependence of the lock-in time on the initial configuration of the rotor-router mechanism. The case study is performed in the form of a game between a player pl intending to lock-in the agent in an Euler tour as quickly as possible and its adversary ad with the counter objective. First, we observe that in certain (easy) cases the lock-in can be achieved in time O(m). On the other hand we show that if adversary ad is solely responsible for the assignment of ports and pointers, the lock-in time Omega(m diam) can be enforced in any graph with m edges and diameter diam. Furthermore, we show that if ad provides its own port numbering after the initial setup of pointers by pl, the complexity of the lock-in problem is bounded by O(m min{log m,diam}). We also propose a class of graphs in which the lock-in requires time Omega(m log m). In the remaining two cases we show that the lock-in requires time Omega(m diam) in graphs with the worst-case topology. In addition, however, we present non-trivial classes of graphs with a large diameter in which the lock-in time is O(m).

Published
2009

15. The Reduced Automata Technique for Graph Exploration Space Lower Bounds

Author

Sergio Rajsbaum, David Ilcinkas, Pierre Fraigniaud, Sébastien Tixeuil, Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Instituto de Matematicas [México], Universidad Nacional Autónoma de México (UNAM), See paper for details., Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman

Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Finite-state machine, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Graph theory, robot, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Upper and lower bounds, Graph, Directed cycle, Automaton, finite automaton, Combinatorics, Computer Science::Robotics, Graph exploration, 010201 computation theory & mathematics, Search algorithm, mobile agent, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract

We consider the task of exploring graphs with anonymous nodes by a team of non-cooperative robots, modeled as finite automata. For exploration to be completed, each edge of the graph has to be traversed by at least one robot. In this paper, the robots have no a priori knowledge of the topology of the graph, nor of its size, and we are interested in the amount of memory the robots need to accomplish exploration, We introduce the so-called {\em reduced automata technique}, and we show how to use this technique for deriving several space lower bounds for exploration. Informally speaking, the reduced automata technique consists in reducing a robot to a simpler form that preserves its “core” behavior on some graphs. Using this technique, we first show that any set of $q\geq 1$ non-cooperative robots, requires $\Omega(\log(\frac{n}{q}))$ memory bits to explore all $n$-node graphs. The proof implies that, for any set of $q K$-state robots, there exists a graph of size $O(qK)$ that no robot of this set can explore, which improves the $O(K^{O(q)})$ bound by Rollik (1980). Our main result is an application of this latter result, concerning {\em terminating} graph exploration with one robot, i.e., in which the robot is requested to stop after completing exploration. For this task, the robot is provided with a pebble, that it can use to mark nodes (without such a marker, even terminating exploration of cycles cannot be achieved). We prove that terminating exploration requires $\Omega(\log n)$ bits of memory for a robot achieving this task in all $n$-node graphs.

Published
2006

16. Labeling Schemes for Tree Representation

Author

David Ilcinkas, David Peleg, Pierre Fraigniaud, Amos Korman, Reuven Cohen, Department of Computer Science and Applied Mathematics [Rehovot], Weizmann Institute of Science [Rehovot, Israël], Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Pierre Fraigniaud and David Ilcinkas were supported by project ``PairAPair' of the ACI Masses de Données, project ``Fragile' of the ACI Sécurité et Informatique, and project ``Grand Large' of INRIA., Ajit Pal, Ajay D. Kshemkalyani, Rajeev Kumar, Arobinda Gupta, Department of Electrical and Computer Engineering [Boston University] (ECE), Boston University [Boston] (BU), Technion - Israel Institute of Technology [Haifa], See paper for details., and ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007)

Subjects
K-ary tree, General Computer Science, Symmetric graph, Edge-graceful labeling, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Combinatorics, symbols.namesake, 0202 electrical engineering, electronic engineering, information engineering, Connectivity, Mathematics, Minimum degree spanning tree, Discrete mathematics, spanning tree, Spanning tree, Applied Mathematics, Shortest-path tree, Complete graph, 020206 networking & telecommunications, 020207 software engineering, Numbering, Labeling scheme, Computer Science Applications, Planar graph, tree representation, Tree structure, 010201 computation theory & mathematics, symbols, Regular graph, Gomory–Hu tree
Abstract

International audience; This paper deals with compact label-based representations for trees. Consider an $n$-node undirected connected graph $G$ with a predefined numbering on the ports of each node. The {\em all-ports} tree labeling $\cL_{all}$ gives each node $v$ of $G$ a label containing the port numbers of all the {\em tree} edges incident to $v$. The {\em upward} tree labeling $\cL_{up}$ labels each node $v$ by the number of the port leading from $v$ to its parent in the tree. Our measure of interest is the worst case and total length of the labels used by the scheme, denoted $M_{up}(T)$ and $S_{up}(T)$ for $\cL_{up}$ and $M_{all}(T)$ and $S_{all}(T)$ for $\cL_{all}$. The problem studied in this paper is the following: Given a graph $G$ and a predefined port labeling for it, with the ports of each node $v$ numbered by $0,\ldots,\deg(v)-1$, select a rooted spanning tree for $G$ minimizing (one of) these measures. We show that the problem is polynomial for $M_{up}(T)$, $S_{up}(T)$ and $S_{all}(T)$ but NP-hard for $M_{all}(T)$ (even for 3-regular planar graphs). We show that for every graph $G$ and port numbering there exists a spanning tree $T$ for which $S_{up}(T) = O(n\log\log n)$. We give a tight bound of $O(n)$ in the cases of complete graphs with arbitrary labeling and arbitrary graphs with symmetric port assignments. We conclude by discussing some applications for our tree representation schemes.

Published
2005

17. A Solution to a Problem of D. Lau: Complete Classification of Intervals in the Lattice of Partial Boolean Clones

Author

Karsten Schölzel, Miguel Couceiro, Lucien Haddad, Tamás Waldhauser, Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Knowledge representation, reasonning (ORPAILLEUR), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Natural Language Processing & Knowledge Discovery (LORIA - NLPKD), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Royal Military College of Canada (RMCC), Royal Military College of Canada, Mathematics Research Unit, University of Luxembourg [Luxembourg], Bolyai Institute [Szeged], University of Szeged [Szeged], Université du Luxembourg (Uni.lu), and The authors thank the anonymous referees for their valuable comments on the previous version of this paper. L. Haddad is supported by Academic Research Program of RMC. K. Sch¨olzel is supported by the internal research project MRDO2 of the University of Luxembourg. T. Waldhauser acknowledges that the present project is supported by the Hungarian National Foundation for Scientific Research under grants no. K83219 and K104251. The present project is supported by the European Union and co-funded by the European Social Fund under the project 'Telemedicine-focused research activities on the field of Mathematics, Informatics and Medical sciences' of project number 'TAMOP-4.2.2.A-11/1/KONV-2012-0073'.

Subjects
Discrete mathematics, 021103 operations research, Parity function, Two-element Boolean algebra, 010102 general mathematics, 0211 other engineering and technologies, 02 engineering and technology, Boolean algebras canonically defined, Complete Boolean algebra, 01 natural sciences, Combinatorics, Boolean domain, Maximum satisfiability problem, Free Boolean algebra, Boolean expression, [INFO]Computer Science [cs], 0101 mathematics, [MATH]Mathematics [math], Mathematics
Abstract

International audience; The following natural problem, first considered by D. Lau, has been tackled by several authors recently: Let C be a total clone on 2 := {0, 1}. Describe the interval I(C) of all partial clones on 2 whose total component is C. We establish some results in this direction and combine them with previous ones to show the following dichotomy result: For every total clone C on 2, the set I(C) is either finite or of continuum cardinality. 1. Preliminaries Let k ≥ 2 be an integer and let k be a k-element set. Without loss of generality we assume that k := {0,. .. , k − 1}. For a positive integer n, an n-ary partial function on k is a map f : dom (f) → k where dom (f) is a subset of k n , called the domain of f. Let Par (n) (k) denote the set of all n-ary partial functions on k and let Par(k) := n≥1