Search

Showing total 17 results
Start Over Topic discrete mathematics
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
Full Text
View/download PDF

2. 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
Full Text
View/download PDF

3. On the complexity of computing integral bases of function fields

Author

Simon Abelard, Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), David R. Cheriton School of Computer Science, University of Waterloo [Waterloo], This paper is a part of a project that has received funding by the French Agence de l'Innovation de Défense (DGA)., Boulier F., England M., Sadykov T.M., and Vorozhtsov E.V.

Subjects
Algebraic function field, Computer Science - Symbolic Computation, FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], 050101 languages & linguistics, Plane curve, [MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC], 02 engineering and technology, Symbolic Computation (cs.SC), Commutative Algebra (math.AC), Puiseux series, Mathematics - Algebraic Geometry, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, Polynomial matrices, 0202 electrical engineering, electronic engineering, information engineering, FOS: Mathematics, 0501 psychology and cognitive sciences, Linear algebra, Algebraic Geometry (math.AG), Mathematics, Discrete mathematics, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Irreducible polynomial, 05 social sciences, Basis (universal algebra), Function (mathematics), Mathematics - Commutative Algebra, 020201 artificial intelligence & image processing, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], Monic polynomial
Abstract

Let $\mathcal{C}$ be a plane curve given by an equation $f(x,y)=0$ with $f\in K[x][y]$ a monic squarefree polynomial. We study the problem of computing an integral basis of the algebraic function field $K(\mathcal{C})$ and give new complexity bounds for three known algorithms dealing with this problem. For each algorithm, we study its subroutines and, when it is possible, we modify or replace them so as to take advantage of faster primitives. Then, we combine complexity results to derive an overall complexity estimate for each algorithm. In particular, we modify an algorithm due to B\"ohm et al. and achieve a quasi-optimal runtime., Comment: Preliminary version

Published
2020
Full Text
View/download PDF

4. 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
Full Text
View/download PDF

5. 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
Full Text
View/download PDF

6. 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
Full Text
View/download PDF

7. The cost of monotonicity in distributed graph searching

Author

Nicolas Nisse, David Soguet, David Ilcinkas, Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Additional supports from the project 'Fragile' of the ACI Sécurité Informatique, and from the project 'Grand Large' of INRIA., Eduardo Tovar, Philippas Tsigas, Hacène Fouchal, 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), 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
Monotonicity, Mathematical optimization, Theoretical computer science, Computer Networks and Communications, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 050801 communication & media studies, 0102 computer and information sciences, 02 engineering and technology, Strength of a graph, Biconnected graph, 01 natural sciences, Theoretical Computer Science, law.invention, 0508 media and communications, Graph power, law, Line graph, 0202 electrical engineering, electronic engineering, information engineering, Graph property, Complement graph, Graph searching, Distance-hereditary graph, Mobile agent, Discrete mathematics, 020203 distributed computing, 05 social sciences, Voltage graph, Directed graph, Butterfly graph, Competitive ratio, Graph bandwidth, Computational Theory and Mathematics, 010201 computation theory & mathematics, Hardware and Architecture, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Null graph, Graph factorization, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

International audience; Blin {\it et al.} (2006) proposed a distributed protocol that enables the smallest number of searchers to clear any unknown asynchronous graph in a decentralized manner. {\it Unknown} means that the searchers are provided no {\it a priori} information about the graph. However, the strategy that is actually performed lacks of an important property, namely the monotonicity. That is, the clear part of the graph may decrease at some steps of the execution of the protocol. Actually, the protocol of Blin {\it et al.} is executed in exponential time. Nisse and Soguet (2007) proved that, in order to ensure the smallest number of searchers to clear any $n$-node graph in a monotone way, it is necessary and sufficient to provide $\Theta(n \log n)$ bits of information to the searchers by putting short labels on the nodes of the graph. This paper deals with the smallest number of searchers that are necessary and sufficient to monotoneously clear any graph in a decentralized manner, when the searchers have no a priori information about the graph. The distributed graph searching problem considers a team of searchers that is aiming at clearing any connected contaminated graph. The clearing of the graph is required to be {\it connected}, i.e., the clear part of the graph must remain permanently connected, and {\it monotone}, i.e., the clear part of the graph only grows. The {\it search number} $\mcs(G)$ of a graph $G$ is the smallest number of searchers necessary to clear $G$ in a monotone connected way in centralized settings. We prove that any distributed protocol aiming at clearing any unknown n-node graph in a monotone connected way, in decentralized settings, has {\it competitive ratio} $\Theta(\frac{n}{\log n})$. That is, we prove that, for any distributed protocol $\cal P$, there exists a constant $c$ such that for any sufficiently large $n$, there exists a $n$-node graph $G$ such that $\cal P$ requires at least $c\frac{n}{\log n}\, \mcs(G)$ searchers to clear $G$. Moreover, we propose a distributed protocol that allows $O(\frac{n}{\log n})\, \mcs(G)$ searchers to clear any unknown asynchronous $n$-node graph $G$ in a monotone connected way.

Published
2009
Full Text
View/download PDF

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
Full Text
View/download PDF

9. Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Networks

Author

Christian Glacet, Nicolas Hanusse, Colette Johnen, David Ilcinkas, 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-16-CE40-0023,DESCARTES,Abstraction modulaire pour le calcul distribué(2016), ANR-16-CE25-0009,ESTATE,Auto-stabilisation et amélioration de la sûreté dans les environnements distribués évoluant dans le temps(2016), ANR-10-IDEX-0003,IDEX BORDEAUX,Initiative d'excellence de l'Université de Bordeaux(2010), See paper for details., and ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011)

Subjects
Routing protocol, Leader election, Theoretical computer science, Computer Networks and Communications, Computer science, 02 engineering and technology, Theoretical Computer Science, Artificial Intelligence, shortest-path, disconnected network, Node (computer science), 0202 electrical engineering, electronic engineering, information engineering, Mathematics, Discrete mathematics, Connected component, routing algorithm, business.industry, Shortest-path tree, 020206 networking & telecommunications, Task (computing), Tree (data structure), self-stabilization, Hardware and Architecture, Asynchronous communication, Shortest path problem, 020201 artificial intelligence & image processing, Enhanced Data Rates for GSM Evolution, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Daemon, business, Software, Computer network
Abstract

Many articles deal with the problem of maintaining a rooted shortest-path tree. However, after some edge deletions, some nodes can be disconnected from the connected component V r of some distinguished node r . In this case, an additional objective is to ensure the detection of the disconnection by the nodes that no longer belong to V r . We present a detailed analysis of a silent self-stabilizing algorithm. We prove that it solves this more demanding task in anonymous weighted networks with the following additional strong properties: it runs without any knowledge on the network and under the unfair daemon, that is without any assumption on the asynchronous model. Moreover, it terminates in less than 2 n + D rounds for a network of n nodes and hop-diameter D .

Published
2014
Full Text
View/download PDF

10. 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
Full Text
View/download PDF

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
Full Text
View/download PDF

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

Author

Ahmed Mouhamadou Wade, David Ilcinkas, 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), 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-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), and Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest

Subjects
Mobile agent, Discrete mathematics, PV-graph, Class (set theory), Computer science, business.industry, Distributed computing, Multiplicative function, Context (language use), 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Power (physics), Set (abstract data type), 010201 computation theory & mathematics, Public transport, 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], business, Time complexity, Dynamic graphs
Abstract

International audience; We study the problem of exploration by a mobile entity (agent) of a class of dynamic networks, namely the periodically-varying graphs (the PV-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 (ISAAC 2009) 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 number of steps (and thus of moves) to explore a n-node PV-graph of k carriers and maximal period p is in Theta(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 worst-case optimal number of moves by a multiplicative factor of at least Theta(p), while the time complexity is reduced to Theta(n p). (In any connected PV-graph, we have n < k p$.) We also show some complementary optimal results in specific cases (same period for all carriers, highly connected PV-graphs). Finally this new ability allows the agent to completely map the PV-graph, in addition to just explore it.

Published
2011
Full Text
View/download PDF

13. Optimal Exploration of Terrains with Obstacles

Author

Andrzej Pelc, Jurek Czyzowicz, David Ilcinkas, Arnaud Labourel, 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), 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), 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
FOS: Computer and information sciences, Convex hull, 0209 industrial biotechnology, Matching (graph theory), Computer science, Terrain, 0102 computer and information sciences, 02 engineering and technology, Computer Science::Computational Geometry, exploration, mobile robot, 01 natural sciences, Computer Science::Robotics, 020901 industrial engineering & automation, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Point (geometry), obstacle, Discrete mathematics, Mobile robot, polygon, Computer Science::Graphics, 010201 computation theory & mathematics, Polygon, Trajectory, Robot, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract

International audience; A mobile robot represented by a point moving in the plane has to explore an unknown flat terrain with impassable obstacles. Both the terrain and the obstacles are modeled as arbitrary polygons. We consider two scenarios: the unlimited vision, when the robot situated at a point p of the terrain explores (sees) all points q of the terrain for which the segment pq belongs to the terrain, and the limited vision, when we require additionally that the distance between p and q be at most 1. All points of the terrain (except obstacles) have to be explored and the performance of an exploration algorithm, called its complexity, is measured by the length of the trajectory of the robot. For unlimited vision we show an exploration algorithm with complexity $O(P+D\sqrt{k})$, where P is the total perimeter of the terrain (including perimeters of obstacles), D is the diameter of the convex hull of the terrain, and k is the number of obstacles. We do not assume knowledge of these parameters. We also prove a matching lower bound showing that the above complexity is optimal, even if the terrain is known to the robot. For limited vision we show exploration algorithms with complexity $O(P+A+\sqrt{Ak})$, where A is the area of the terrain (excluding obstacles). Our algorithms work either for arbitrary terrains, if one of the parameters A or k is known, or for c-fat terrains, where c is any constant (unknown to the robot) and no additional knowledge is assumed. (A terrain ${\mathcal T}$ with obstacles is c-fat if R/r ≤ c, where R is the radius of the smallest disc containing ${\mathcal T}$ and r is the radius of the largest disc contained in ${\mathcal T}$.) We also prove a matching lower bound $\Omega(P+A+\sqrt{Ak})$ on the complexity of exploration for limited vision, even if the terrain is known to the robot.

Published
2010
Full Text
View/download PDF

14. Almost Optimal Asynchronous Rendezvous in Infinite Multidimensional Grids

Author

Jurek Czyzowicz, Evangelos Bampas, Leszek Gąsieniec, David Ilcinkas, Arnaud Labourel, 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), 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), 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
Discrete mathematics, Mathematical optimization, 021103 operations research, Euclidean space, Dimension (graph theory), 0211 other engineering and technologies, Rendezvous, 0102 computer and information sciences, 02 engineering and technology, Grid, 01 natural sciences, Upper and lower bounds, law.invention, Computer Science::Multiagent Systems, 010201 computation theory & mathematics, law, Position (vector), rendezvous, Cartesian coordinate system, mobile agents, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Rendezvous problem, Mathematics
Abstract

International audience; Two anonymous mobile agents (robots) moving in an asynchronous manner have to meet in an infinite grid of dimension $\dime > 0$, starting from two arbitrary positions at distance at most $d$. Since the problem is clearly infeasible in such general setting, we assume that the grid is embedded in a $\dime$-dimensional Euclidean space and that each agent knows the Cartesian coordinates of its own initial position (but not the one of the other agent). We design an algorithm permitting the agents to meet after traversing a trajectory of length $O(d^\dime{\rm polylog\ }d)$. This bound for the case of {\sc 2d}~-grids subsumes the main result of \cite{CCGL}. The algorithm is almost optimal, since the $\Omega(d^\dime)$ lower bound is straightforward. Further, we apply our rendezvous method to the following network design problem. The ports of the $\dime$-dimensional grid have to be set such that two anonymous agents starting at distance at most $d$ from each other will always meet, moving in an asynchronous manner, after traversing a $O(d^\dime{\rm polylog\ }d)$ length trajectory. We can also apply our method to a version of the geometric rendezvous problem. Two anonymous agents move asynchronously in the $\dime$-dimensional Euclidean space. The agents have the radii of visibility of $r_1$ and $r_2$, respectively. Each agent knows only its own initial position and its own radius of visibility. The agents meet when one agent is visible to the other one. We propose an algorithm designing the trajectory of each agent, so that they always meet after traveling a total distance of $O((\frac{d}{r})^\dime {\rm polylog}(\frac{d}{r}))$, where $r = \min(r_1, r_2)$ and for $r\geq 1$.

Published
2010
Full Text
View/download PDF

15. Label-Guided Graph Exploration by a Finite Automaton

Author

David Ilcinkas, David Peleg, Amos Korman, Pierre Fraigniaud, Reuven Cohen, Department of Electrical and Computer Engineering [Boston University] (ECE), Boston University [Boston] (BU), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), 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), 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), Department of Computer Science and Applied Mathematics [Rehovot], Weizmann Institute of Science [Rehovot, Israël], See paper for details, ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Reuven Cohen was supported by the Pacific Theaters Foundation. Pierre Fraigniaud and David Ilcinkas were supported by the project ``PairAPair' of the ACI Masses de Données, the project ``Fragile' of the ACI Sécurité et Informatique, and by the project ``Grand Large' of INRIA., L. Caires, G. Italiano, L. Monteiro, C. Palamidessi, M. Yung, Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest

Subjects
Theoretical computer science, Graph labeling, Computer science, Labeling schemes, Symmetric graph, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Simplex graph, law.invention, Computer Science::Robotics, Mathematics (miscellaneous), Graph exploration, Graph power, law, Clique-width, Line graph, String graph, 0202 electrical engineering, electronic engineering, information engineering, Graph property, Lattice graph, Time complexity, Complement graph, Mathematics, Forbidden graph characterization, Discrete mathematics, Degree (graph theory), Visibility graph, Voltage graph, Quartic graph, Graph theory, Butterfly graph, Graph, Finite graph, Vertex-transitive graph, Graph bandwidth, 010201 computation theory & mathematics, Bounded function, Cubic graph, Distributed algorithms, 020201 artificial intelligence & image processing, Regular graph, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Null graph, ACM C.2.1, ACM C.2.2, ACM C.2.4, ACM E.1
Abstract

A finite automaton, simply referred to as a robot , has to explore a graph, that is, visit all the nodes of the graph. The robot has no a priori knowledge of the topology of the graph, nor of its size. It is known that for any k -state robot, there exists a graph of maximum degree 3 that the robot cannot explore. This article considers the effects of allowing the system designer to add short labels to the graph nodes in a preprocessing stage, for helping the exploration by the robot. We describe an exploration algorithm that, given appropriate 2-bit labels (in fact, only 3-valued labels), allows a robot to explore all graphs. Furthermore, we describe a suitable labeling algorithm for generating the required labels in linear time. We also show how to modify our labeling scheme so that a robot can explore all graphs of bounded degree, given appropriate 1-bit labels. In other words, although there is no robot able to explore all graphs of maximum degree 3, there is a robot R, and a way to color in black or white the nodes of any bounded-degree graph G , so that R can explore the colored graph G . Finally, we give impossibility results regarding graph exploration by a robot with no internal memory (i.e., a single-state automaton).

Published
2008
Full Text
View/download PDF

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
Full Text
View/download PDF

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

Full Text
View/download PDF