Author: "Networks, Graphs and Algorithms (GANG)" - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"Networks, Graphs and Algorithms (GANG)"' showing total 290 results

Start Over Author "Networks, Graphs and Algorithms (GANG)"

290 results on '"Networks, Graphs and Algorithms (GANG)"'

1. Decomposing a Graph into Shortest Paths with Bounded Eccentricity

Author: Laurent Viennot, Fabien de Montgolfier, Etienne Birmelé, Léo Planche, Mathématiques Appliquées Paris 5 (MAP5 - UMR 8145), Université Paris Descartes - Paris 5 (UPD5)-Institut National des Sciences Mathématiques et de leurs Interactions (INSMI)-Centre National de la Recherche Scientifique (CNRS), 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), Laboratory of Information, Network and Communication Sciences (LINCS), Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT), Institut Mines-Télécom [Paris] (IMT)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Pierre et Marie Curie - Paris 6 (UPMC), Planche, Léo, Mathématiques Appliquées à Paris 5 ( MAP5 - UMR 8145 ), Université Paris Descartes - Paris 5 ( UPD5 ) -Institut National des Sciences Mathématiques et de leurs Interactions-Centre National de la Recherche Scientifique ( CNRS ), Institut de Recherche en Informatique Fondamentale ( IRIF ), 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 ), Laboratory of Information, Network and Communication Sciences ( LINCS ), Université Pierre et Marie Curie - Paris 6 ( UPMC ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut Mines-Télécom [Paris], MAP5 - Mathématiques Appliquées à Paris 5 (MAP5), Centre National de la Recherche Scientifique (CNRS) - Institut National des Sciences Mathématiques et de leurs Interactions - Université Paris Descartes - Paris 5 (UPD5), Institut de Recherche en Informatique Fondamentale (IRIF), 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) - 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), and Université Pierre et Marie Curie - Paris 6 (UPMC) - Institut National de Recherche en Informatique et en Automatique (Inria) - Institut Mines-Télécom [Paris]
Subjects: Graph center, Graph Clustering, BFS, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, MESP, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 02 engineering and technology, 0102 computer and information sciences, Strength of a graph, Graph Decomposition, 01 natural sciences, law.invention, Combinatorics, 03 medical and health sciences, 0302 clinical medicine, law, Line graph, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, [ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Complement graph, Mathematics, Discrete mathematics, 000 Computer science, knowledge, general works, Applied Mathematics, Distance Labeling, 020207 software engineering, 16. Peace & justice, Tree decomposition, Butterfly graph, Modular decomposition, 010201 computation theory & mathematics, 030220 oncology & carcinogenesis, Computer Science, Null graph
Abstract: International audience; We introduce the problem of hub-laminar decomposition which generalizes that of computing a shortest path with minimum eccentricity (MESP). Intuitively, it consists in decomposing a graph into several paths that collectively have small eccentricity and meet only near their extremities. The problem is related to computing an isometric cycle with minimum eccentricity (MEIC). It is also linked to DNA reconstitution in the context of metagenomics in biology. We show that a graph having such a decomposition with long enough paths can be decomposed in polynomial time with approximated guaranties on the parameters of the decomposition. Moreover, such a decomposition with few paths allows to compute a compact representation of distances with additive distortion. We also show that having an isometric cycle with small eccentricity is related to the possibility of embedding the graph in a cycle with low distortion.
Published: 2017

2. Error-sensitive proof-labeling schemes

Author: Laurent Feuilloley, Pierre Fraigniaud, Networks, Graphs and Algorithms (GANG), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), 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), and Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, 000 Computer science, knowledge, general works, Computer Science - Distributed, Parallel, and Cluster Computing, Artificial Intelligence, Computer Networks and Communications, Hardware and Architecture, Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Software, Theoretical Computer Science
Abstract: International audience; Proof-labeling schemes are known mechanisms providing nodes of networks with certificates that can be verified locally by distributed algorithms. Given a boolean predicate on network states, such schemes enable to check whether the predicate is satisfied by the actual state of the network, by having nodes interacting with their neighbors only. Proof-labeling schemes are typically designed for enforcing fault-tolerance, by making sure that if the current state of the network is illegal with respect to some given predicate, then at least one node will detect it. Such a node can raise an alarm, or launch a recovery procedure enabling the system to return to a legal state. In this paper, we introduce error-sensitive proof-labeling schemes. These are proof-labeling schemes which guarantee that the number of nodes detecting illegal states is linearly proportional to the edit-distance between the current state and the set of legal states. By using error-sensitive proof-labeling schemes, states which are far from satisfying the predicate will be detected by many nodes, enabling fast return to legality. We provide a structural characterization of the set of boolean predicates on network states for which there exist error-sensitive proof-labeling schemes. This characterization allows us to show that classical predicates such as, e.g., acyclicity, and leader admit error-sensitive proof-labeling schemes, while others like regular subgraphs don't. We also focus on compact error-sensitive proof-labeling schemes. In particular, we show that the known proof-labeling schemes for spanning tree and minimum spanning tree, using certificates on O(logn) bits, and on O(log2n) bits, respectively, are error-sensitive, as long as the trees are locally represented by adjacency lists, and not just by parent pointers.
Published: 2022

3. Neural Network Information Leakage through Hidden Learning

Author: Arthur Carvalho Walraven da Cunha, Emanuele Natale, Laurent Viennot, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), 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 (1965 - 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 (1965 - 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), Centre National de la Recherche Scientifique (CNRS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), 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), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), OPAL-Meso, COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), 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)-Inria Sophia Antipolis - Méditerranée (CRISAM), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Inria, CNRS, I3S, and Université Côte d'Azur
Subjects: Artificial Neural Network, Hidden computation, Information security, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG]
Abstract: We investigate the problem of making a neural network perform some hidden computation whose result can be easily retrieved from the network output. In particular, we consider the following scenario. A user is provided a neural network for a classification task by a company. We further assume that the company has limited access to the user's computation, and can only observe the output of the network when the user evaluates it. The user's input to the network contains some sensible information. We provide a simple and efficient training procedure, called Hidden Learning, that produces two networks such that i) One of the networks solves the original classification task with comparable performance to state of the art solutions of the task; ii) The other network takes as input the output of the first and solves another classification task that retrieves the sensible information with considerable accuracy. Our result might expose important issues from an information security point of view, as for the use of artificial neural networks in sensible applications.
Published: 2023

4. Minimum Eccentricity Shortest Path Problem: an Approximation Algorithm and Relation with the k-Laminarity Problem

Author: Fabien de Montgolfier, Léo Planche, Etienne Birmelé, Mathématiques Appliquées Paris 5 (MAP5 - UMR 8145), Université Paris Descartes - Paris 5 (UPD5)-Institut National des Sciences Mathématiques et de leurs Interactions (INSMI)-Centre National de la Recherche Scientifique (CNRS), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), MAC2 (Idex USPC), MAC2, 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), Mathématiques Appliquées à Paris 5 ( MAP5 - UMR 8145 ), Université Paris Descartes - Paris 5 ( UPD5 ) -Institut National des Sciences Mathématiques et de leurs Interactions-Centre National de la Recherche Scientifique ( CNRS ), Institut de Recherche en Informatique Fondamentale ( IRIF ), 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, and Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria )
Subjects: FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], k-Laminar Graph, BFS, Discrete Mathematics (cs.DM), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, Computational Complexity (cs.CC), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Graph search, 01 natural sciences, Eccentricity, Combinatorics, Diameter, 0202 electrical engineering, electronic engineering, information engineering, Yen's algorithm, [ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Mathematics, Discrete mathematics, [ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM], Longest path problem, Widest path problem, Graph theory, Computer Science - Computational Complexity, Euclidean shortest path, [ INFO.INFO-CC ] Computer Science [cs]/Computational Complexity [cs.CC], Shortest Path Faster Algorithm, 010201 computation theory & mathematics, Shortest path problem, 020201 artificial intelligence & image processing, K shortest path routing, Approximation Algorithms, Distance, Computer Science - Discrete Mathematics
Abstract: International audience; The Minimum Eccentricity Shortest Path (MESP) Problem consists in determining a shortest path (a path whose length is the distance between its extremities) of minimum eccentricity in a graph. It was introduced by Dragan and Leitert [9] who described a linear-time algorithm which is an 8-approximation of the problem. In this paper, we study deeper the double-BFS procedure used in that algorithm and extend it to obtain a linear-time 3-approximation algorithm. We moreover study the link between the MESP problem and the notion of laminarity, introduced by Völkel et al [12], corresponding to its restriction to a diameter (i.e. a shortest path of maximum length), and show tight bounds between MESP and laminarity parameters.
Published: 2016

5. On a Generalization of the Ryser-Brualdi-Stein Conjecture

Author: Charbit, Pierre, Aharoni, Ron, Howard, David, Laboratoire d'informatique Algorithmique : Fondements et Applications ( LIAFA ), 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 Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ), Department of Mathematics ( TECHNION ), Technion - Israel Institute of Technology [Haifa], Colgate University, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), 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 Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Department of Mathematics (TECHNION)
Subjects: FOS: Computer and information sciences, Mathematics::Combinatorics, Discrete Mathematics (cs.DM), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [ MATH.MATH-CO ] Mathematics [math]/Combinatorics [math.CO], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), ComputingMilieux_MISCELLANEOUS, [ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Computer Science - Discrete Mathematics
Abstract: A rainbow matching for (not necessarily distinct) sets F_1,...,F_k of hypergraph edges is a matching consisting of k edges, one from each F_i. The aim of the paper is twofold - to put order in the multitude of conjectures that relate to this concept (some of them first presented here), and to present some partial results on one of these conjectures, that seems central among them.
Published: 2015

6. On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols

Author: Adrian Kosowski, Przemyslaw Uznanski, Leszek Gasieniec, Jurek Czyzowicz, Paul G. Spirakis, Evangelos Kranakis, Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), Department of Computer Science [Liverpool], University of Liverpool, Networks, Graphs and Algorithms (GANG), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), School of Computer Science [Ottawa], Carleton University, Research Academic Computer Technology institute [Patras] (RA-CTI), Department of Information and Computer Science [Aalto], Helsinki Institute for Information Technology (HIIT), Aalto University-University of Helsinki-Aalto University-University of Helsinki, ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), and Helsingin yliopisto = Helsingfors universitet = University of Helsinki-Aalto University-Helsingin yliopisto = Helsingfors universitet = University of Helsinki-Aalto University
Subjects: FOS: Computer and information sciences, education.field_of_study, General Computer Science, Discrete dynamics, Computer Networks and Communications, Applied Mathematics, Population, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Type (model theory), Theoretical Computer Science, Combinatorics, Computational Theory and Mathematics, Linear term, Convergence (routing), Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), education, Natural class, Mathematics
Abstract: International audience; In this work we focus on a natural class of population protocols whose dynamics are modelled by the discrete version of Lotka-Volterra equations. In such protocols, when an agent $a$ of type (species) $i$ interacts with an agent $b$ of type (species) $j$ with $a$ as the initiator, then $b$'s type becomes $i$ with probability $P_{ij}$. In such an interaction, we think of $a$ as the predator, $b$ as the prey, and the type of the prey is either converted to that of the predator or stays as is. Such protocols capture the dynamics of some opinion spreading models andgeneralize the well-known Rock-Paper-Scissors discrete dynamics. We consider the pairwise interactions among agents that are scheduled uniformly at random.We start by considering the convergence time and show that any Lotka-Volterra-type protocol on an $n$-agent population converges to some absorbing state in time polynomial in $n$, w.h.p., when any pair of agents is allowed to interact. By contrast, when the interaction graph is a star, even the Rock-Paper-Scissors protocol requires exponential time to converge. We then study threshold effects exhibited by Lotka-Volterra-type protocols with 3 and more species under interactions between any pair of agents. We start by presenting a simple 4-type protocol in which the probability difference of reaching the two possible absorbing states is strongly amplified by the ratio of the initial populations of the two other types, which are transient, but ``control'' convergence. We then prove that the Rock-Paper-Scissors protocol reaches each of its three possible absorbing states with almost equal probability, starting from any configuration satisfying some sub-linear lower bound on the initial size of each species. That is, Rock-Paper-Scissors is a realization of a ``coin-flip consensus'' in a distributed system. Some of our techniques may be of independent value.
Published: 2022

7. New Encodings of Pseudo-Boolean Constraints into CNF

Author: Olivier Roussel, Yacine Boufkhad, Olivier Bailleux, Laboratoire Informatique de Recherche sur les Systèmes Intelligents et leurs Applications (LIRSIA), Université de Bourgogne (UB), Networks, Graphs and Algorithms (GANG), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Informatique de Lens (CRIL), Université d'Artois (UA)-Centre National de la Recherche Scientifique (CNRS), Boufkhad, Yacine, Laboratoire Informatique de Recherche sur les Systèmes Intelligents et leurs Applications ( LIRSIA ), Université de Bourgogne ( UB ), Networks, Graphs and Algorithms ( GANG ), Laboratoire d'informatique Algorithmique : Fondements et Applications ( LIAFA ), Université Paris Diderot - Paris 7 ( UPD7 ) -Centre National de la Recherche Scientifique ( CNRS ) -Université Paris Diderot - Paris 7 ( UPD7 ) -Centre National de la Recherche Scientifique ( CNRS ) -Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ), Université Paris Diderot - Paris 7 ( UPD7 ) -Centre National de la Recherche Scientifique ( CNRS ), Centre de Recherche en Informatique de Lens ( CRIL ), and Université d'Artois ( UA ) -Centre National de la Recherche Scientifique ( CNRS )
Subjects: Discrete mathematics, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Polynomial, 021103 operations research, Unit propagation, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 02 engineering and technology, Computer Science::Computational Complexity, Expressive power, Exponential function, Combinatorics, [ INFO.INFO-CC ] Computer Science [cs]/Computational Complexity [cs.CC], Encoding (memory), 0202 electrical engineering, electronic engineering, information engineering, Local consistency, 020201 artificial intelligence & image processing, Point (geometry), [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], [ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Mathematics
Abstract: International audience; This paper answers affirmatively the open question of the existence of a polynomial size CNF encoding of pseudo-Boolean (PB) constraints such that generalized arc consistency (GAC) is maintained through unit propagation (UP). All previous encodings of PB constraints either did not allow UP to maintain GAC, or were of exponential size in the worst case. This paper presents an encoding that realizes both of the desired properties. From a theoretical point of view, this narrows the gap between the expressive power of clauses and the one of pseudo-Boolean constraints.
Published: 2009

8. Redundancy in distributed proofs

Author: Ami Paz, Mor Perry, Laurent Feuilloley, Juho Hirvonen, Pierre Fraigniaud, 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), Tel Aviv University (TAU), Universidad de Chile, Institut de Recherche en Informatique Fondamentale, Department of Computer Science, University of Vienna, Weizmann Institute of Science, Aalto-yliopisto, Aalto University, Tel Aviv University [Tel Aviv], Schmid, Ulrich, Hirvonen, Juho, Professorship Suomela J., and Tel Aviv University
Subjects: FOS: Computer and information sciences, Theoretical computer science, Correctness, Proof-labeling schemes, Computer Networks and Communications, Computer science, 0102 computer and information sciences, 02 engineering and technology, Gas meter prover, Mathematical proof, 01 natural sciences, Article, Theoretical Computer Science, 0202 electrical engineering, electronic engineering, information engineering, Redundancy (engineering), Nondeterminism, non-determinism, ta113, 000 Computer science, knowledge, general works, Spanning tree, Node (networking), Distributed verification, 020206 networking & telecommunications, Certificate, Space-time tradeoffs, Computer Science - Distributed, Parallel, and Cluster Computing, Computational Theory and Mathematics, 010201 computation theory & mathematics, Hardware and Architecture, Distributed algorithm, Distributed graph algorithms, Computer Science, Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: Distributed proofs are mechanisms enabling the nodes of a network to collectivity and efficiently check the correctness of Boolean predicates on the structure of the network, or on data-structures distributed over the nodes (e.g., spanning trees or routing tables). We consider mechanisms consisting of two components: a \emph{prover} assigning a \emph{certificate} to each node, and a distributed algorithm called \emph{verifier} that is in charge of verifying the distributed proof formed by the collection of all certificates. In this paper, we show that many network predicates have distributed proofs offering a high level of redundancy, explicitly or implicitly. We use this remarkable property of distributed proofs for establishing perfect tradeoffs between the \emph{size of the certificate} stored at every node, and the \emph{number of rounds} of the verification protocol. If we allow every node to communicate to distance at most $t$, one might expect that the certificate sizes can be reduced by a multiplicative factor of at least~$t$. In trees, cycles and grids, we show that such tradeoffs can be established for \emph{all} network predicates, i.e., it is always possible to linearly decrease the certificate size. In arbitrary graphs, we show that any part of the certificates common to all nodes can be evenly redistributed among these nodes, achieving even a better tradeoff: this common part of the certificate can be reduced by the size of a smallest ball of radius $t$ in the network. In addition to these general results, we establish several upper and lower bounds on the certificate sizes used for distributed proofs for spanning trees, minimum-weight spanning trees, diameter, additive and multiplicative spanners, and more, improving and generalizing previous results from the literature.
Published: 2020

9. On the weakest information on failures to solve mutual exclusion and consensus in asynchronous crash-prone read/write systems

Author: Hugues Fauconnier, Michel Raynal, Carole Delporte-Gallet, Networks, Graphs and Algorithms (GANG), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), the World Is Distributed Exploring the tension between scale and coordination (WIDE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), ANR-16-CE40-0023,DESCARTES,Abstraction modulaire pour le calcul distribué(2016), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1)
Subjects: Theoretical computer science, Asynchronous system, Computer Networks and Communications, Process (engineering), Computer science, Message passing, 020206 networking & telecommunications, 02 engineering and technology, Theoretical Computer Science, Artificial Intelligence, Hardware and Architecture, Asynchronous communication, 0202 electrical engineering, electronic engineering, information engineering, A priori and a posteriori, 020201 artificial intelligence & image processing, Mutual exclusion, Impossibility, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Semaphore, Software, ComputingMilieux_MISCELLANEOUS
Abstract: Mutual exclusion and consensus are among the most important coordination problems encountered in asynchronous concurrent systems, whether processes communicate using read/write registers or message passing. Unfortunately, neither can be solved in crash-prone systems, as soon as even a single process may crash. Hence, an important question: which is the weakest information on failures that must be given to the processes so that these problems can be solved whatever the number of crashes. This approach to circumvent impossibility results is known under the name failure detectors. Considering mutual exclusion and consensus in a crash-prone asynchronous system where the processes communicate through read/write registers, this article answers the previous question by presenting two failure detectors. The first, called Quasi-Perfect (QP) allows mutual exclusion to be solved in the presence of any number of process crashes. The second, called Ω ⁎ , allows consensus to be solved in the general model where not all but an a priori unknown subset of processes participates in consensus. In addition to algorithms solving each of the previous problems with the help of the associated failure detector, the article shows that QP and Ω ⁎ provides the weakest information on failures needed to solve mutex exclusion and participant-restricted consensus respectively.
Published: 2021

10. Calcul distribué simple et efficace de la betweenness

Author: Crescenzi, Pierluigi, Fraigniaud, Pierre, Paz, Ami, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Networks, Graphs and Algorithms (GANG), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Fraigniaud, Pierre, Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), and Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)
Subjects: Betweenness centrality, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Protocols réseaux, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Algorithmes distribués, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: International audience; La betweenness est un paramètre de graphes fréquemment utilisé avec succès pour l'analyse de réseaux. Dans le cadre des réseaux d'ordinateurs, ce paramètre a ainsiété utilisé pour répondreà plusieurs objectifs, dont le routage et la répartition de ressources. Toutefois, comme observé par Maccari et al. [INFOCOM 2018], l'utilisation pratique de la betweenness pour l'amélioration de protocols réseaux reste handicapée par l'absence d'algorithmes distribués efficaces pour le calcul de ce paramètre. Cet article résume nos travaux démontrant comment ce problème peut-être résolu, en présentant un algorithm distribué efficace pour le calcul de la betweenness. Cet algorithme peutêtre mis en oeuvre au travers de modificationsélémentaires d'algorithmes de routageà vecteur de distance tels que Bellman-Ford. Le temps de convergence de l'algorithme est proportionnel au diamètre du réseau, tout comme Bellman-Ford. La version complète de ce résumé est disponible dans les actes d'INFOCOM 2020 [CFP20].
Published: 2020

11. Ant collective cognition allows for efficient navigation through disordered environments

Author: Amos Korman, Yoav Rodeh, Aviram Gelblum, Ehud Fonio, Ofer Feinerman, Weizmann Institute of Science [Rehovot, Israël], Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Networks, Graphs and Algorithms (GANG), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), and Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)
Subjects: 0301 basic medicine, Speedup, Theoretical computer science, Computer science, QH301-705.5, Science, collective cognition, Movement, paratrechina longicornis, Context (language use), Environment, Physics of Living Systems, General Biochemistry, Genetics and Molecular Biology, 03 medical and health sciences, 0302 clinical medicine, Cognition, Longhorn crazy ant, Animals, Biology (General), Cooperative Behavior, Maze Learning, social insects, General Immunology and Microbiology, biology, Ecology, Ants, General Neuroscience, Stochastic game, General Medicine, biology.organism_classification, Range (mathematics), Tree traversal, 030104 developmental biology, Collective cognition, Medicine, cooperative transport, Other, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], 030217 neurology & neurosurgery, ant in a labyrinth, Research Article, Spatial Navigation
Abstract: International audience; The cognitive abilities of biological organisms only make sense in the context of their environment. Here, we study longhorn crazy ant collective navigation skills within the context of a semi-natural, randomized environment. Mapping this biological setting into the ‘Ant-in-a-Labyrinth’ framework which studies physical transport through disordered media allows us to formulate precise links between the statistics of environmental challenges and the ants’ collective navigation abilities. We show that, in this environment, the ants use their numbers to collectively extend their sensing range. Although this extension is moderate, it nevertheless allows for extremely fast traversal times that overshadow known physical solutions to the ‘Ant-in-a-Labyrinth’ problem. To explain this large payoff, we use percolation theory and prove that whenever the labyrinth is solvable, a logarithmically small sensing range suffices for extreme speedup. Overall, our work demonstrates the potential advantages of group living and collective cognition in increasing a species’ habitable range.
Published: 2020

12. Phylosystemics: Merging Phylogenomics, Systems Biology, and Ecology to Study Evolution

Author: Watson, A.K., Habib, M., Bapteste, E., Institut de Systématique, Evolution, Biodiversité (ISYEB ), Muséum national d'Histoire naturelle (MNHN)-École pratique des hautes études (EPHE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université des Antilles (UA), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Adaptation, Intégration, Réticulation et Evolution (AIRE), Systématique, adaptation, évolution (SAE), Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Evolution Paris Seine, Université Nice Sophia Antipolis (... - 2019) (UNS), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Université des Antilles et de la Guyane (UAG)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Nice Sophia Antipolis (... - 2019) (UNS), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Université des Antilles et de la Guyane (UAG), 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, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: [SDV]Life Sciences [q-bio], ComputingMilieux_MISCELLANEOUS
Abstract: International audience; We define phylosystemics, a multidisciplinary strategy uniting short timescale interaction studies from systems biologists and ecologists with the longer timescale studies familiar to evolutionary biologists, taking advantage of methods from network sciences. Phylosystemics superimposes evolutionary information on entities/edges forming interaction networks produced by systems biology and ecology. At the molecular level, phylosystemics could provide evidence to infer and to time the evolution of molecular processes within a single branch of a phylogeny, in particular between the first and last common ancestors of a group arising during a major evolutionary transition. At the ecosystemic level, phylosystemics could culminate with the development of multilayer temporal networks encompassing biotic and abiotic interactions, whose analyses could unravel ecological interactions with evolutionary consequences.
Published: 2020

13. Simple and Fast Distributed Computation of Betweenness Centrality

Author: Ami Paz, Pierluigi Crescenzi, Pierre Fraigniaud, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Networks, Graphs and Algorithms (GANG), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Fraigniaud, Pierre, 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)-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), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), and Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)
Subjects: Routing protocol, Social and Information Networks (cs.SI), FOS: Computer and information sciences, Theoretical computer science, Computer science, Computation, [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], Computer Science - Social and Information Networks, 02 engineering and technology, Network topology, Graph, Betweenness centrality, Computer Science - Distributed, Parallel, and Cluster Computing, Distributed algorithm, Convergence (routing), 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Graph (abstract data type), 020201 artificial intelligence & image processing, Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], ComputingMilieux_MISCELLANEOUS, Network analysis
Abstract: Betweenness centrality is a graph parameter that has been successfully applied to network analysis. In the context of computer networks, it was considered for various objectives, ranging from routing to service placement. However, as observed by Maccari et al. [INFOCOM 2018], research on betweenness centrality for improving protocols was hampered by the lack of a usable, fully distributed algorithm for computing this parameter. We resolve this issue by designing an efficient algorithm for computing betweenness centrality, which can be implemented by minimal modifications to any distance-vector routing protocol based on Bellman-Ford. The convergence time of our implementation is shown to be proportional to the diameter of the network.
Published: 2020

14. Aspects of Efficiency in Selected Problems of Computation on Large Graphs

Author: Zou, Mengchuan, Networks, Graphs and Algorithms (GANG), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), 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), Université de Paris, Adrian Kosowski, Michel Habib, and ZOU, Mengchuan
Subjects: Graphes de grande taille, Data query, Problème de recherche, Distributed algorithm, Modular decomposition, Problème de flux maximal, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Hypergraphes, Décomposition modulaire, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Search problem, Max-flow problem, Hypergraphs, Algorithme distribué, Requête de données, Large graphs
Abstract: This thesis presents three works on different aspects of efficiency of algorithm design for large scale graph computations.In the first work, we consider a setting of classical centralized computing, and we consider the question of generalizing modular decompositions and designing time- efficient algorithm for this problem. Modular decomposition, and more broadly module detection, are ways to reveal and analyze modular properties in structured data. As the classical modular decomposition is well studied and have an optimal linear-time algorithm, we firstly study the generalizations of these concepts to hy- pergraphs and present here positive results obtained for three definitions of modular decomposition in hypergraphs from the literature. We also consider the generaliza- tion of allowing errors in classical graph modules and present negative results for two this kind of definitions.The second work focuses on graph data query scenarios. Here the model differs from classical computing scenarios in that we are not designing algorithms to solve an original problem, but we assume that there is an oracle which provides partial information about the solution to the original problem, where oracle queries have time or resource consumption, which we model as costs, and we need to have an algorithm deciding how to efficiently query the oracle to get the exact solution to the original problem, thus here the efficiency is addressing to the query costs. We study the generalized binary search problem for which we compute an efficient query strategy to find a hidden target in graphs. We present the results of our work on approximating the optimal strategy of generalized binary search on weighted trees.Our third work draws attention to the question of memory efficiency. The setup in which we perform our computations is distributed and memory-restricted. Specif- ically, every node stores its local data, exchanging data by message passing, and is able to proceed local computations. This is similar to the LOCAL/CONGEST model in distributed computing, but our model additionally requires that every node can only store a constant number of variables w.r.t. its degree. This model can also describe natural algorithms. We implement an existing procedure of multiplicative reweighting for approximating the maximum s–t flow problem on this model, this type of methodology may potentially provide new opportunities for the field of local or natural algorithms.From a methodological point of view, the three types of efficiency concerns cor- respond to the following types of scenarios: the first one is the most classical one – given the problem, we try to design by hand the more efficient algorithm; the second one, the efficiency is regarded as an objective function – where we model query costs as an objective function, and using approximation algorithm techniques to get a good design of efficient strategy; the third one, the efficiency is in fact posed as a constraint of memory and we design algorithm under this constraint., Cette thèse présente trois travaux liés à la conception d’algorithmes efficaces ap- plicables à des graphes de grande taille.Dans le premier travail, nous nous plaçons dans le cadre du calcul centralisé, et ainsi la question de la généralisation des décompositions modulaires et de la conception d’un algorithme efficace pour ce problème. La décomposition modulaire et la détection de module, sont des moyens de révéler et d’analyser les propriétés modulaires de données structurées. Comme la décomposition modulaire classique est bien étudiée et possède un algorithme de temps linéaire optimal, nous étudions d’abord les généralisations de ces concepts en hypergraphes. C’est un sujet peu étudié mais qui permet de trouver de nouvelles structurations dans les familles de parties. Nous présentons ici des résultats positifs obtenus pour trois définitions de la décomposition modulaire dans les hypergraphes de la littérature. Nous considérons également la généralisation en permettant des erreurs dans les modules de graphes classiques et présentons des résultats négatifs pour deux telles définitions.Le deuxième travail est sur des requêtes de données dans un graphe. Ici, le modèle diffère des scénarios classiques dans le sens que nous ne concevons pas d’algorithmes pour résoudre un problème original, mais nous supposons qu’il existe un oracle four- nissant des informations partielles sur la solution de problème initial, où les oracle ont une consommation de temps ou de ressources de requête que nous modélisons en tant que coûts, et nous avons besoin d’un algorithme décidant comment interroger efficacement l’oracle pour obtenir la solution exacte au problème initial. L’efficacité ici concerne le coût de la requête. Nous étudions un problème de la méthode de di- chotomie généralisée pour lequel nous calculons une stratégie d’interrogation efficace afin de trouver une cible cachée dans le graphe. Nous présentons les résultats de nos travaux sur l’approximation de la stratégie optimale de recherche en dichotomie généralisée sur les arbres pondérés.Notre troisième travail est sur la question de l’efficacité de la mémoire. La config- uration dans laquelle nous étudions sont des calculs distribués et avec la limitation en mémoire. Plus précisément, chaque nœud stocke ses données locales en échangeant des données par transmission de messages et est en mesure de procéder à des calculs locaux. Ceci est similaire au modèle LOCAL / CONGEST en calcul distribué, mais notre modèle requiert en outre que chaque nœud ne puisse stocker qu’un nombre constant de variables w.r.t. son degré. Ce modèle peut également décrire des al- gorithmes naturels. Nous implémentons une procédure existante de repondération multiplicative pour approximer le problème de flux maximal sur ce modèle.D’un point de vue méthodologique, les trois types d’efficacité que nous avons étudiées correspondent aux trois types de scénarios suivants:– Le premier est le plus classique. Considérant un problème, nous essayons de concevoir à la main l’algorithme le plus efficace.– Dans le second, l’efficacité est considérée comme un objectif. Nous mod- élisons les coûts de requête comme une fonction objectif, et utilisons des techniques d’algorithme d’approximation pour obtenir la conception d’une stratégie efficace.– Dans le troisième, l’efficacité est en fait posée comme une contrainte de mémoire et nous concevons un algorithme sous cette contrainte.
Published: 2019

15. Fast Diameter Computation within Split Graphs

Author: Laurent Viennot, Michel Habib, Guillaume Ducoffe, Faculty of Mathematics and Computer Science [Bucuresti], University of Bucharest, National Institute for Research and Development in Informatics [Bucharest], Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Université de Paris, 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), This work was supported by a grant of Romanian Ministry of Research and Innovation CCCDI-UEFISCDI. projectno. 17PCCDI/2018Supported by Inria Gang project-team, and ANR project DISTANCIA (ANR-17-CE40-0015).Supported by Irif laboratory from CNRS and Paris University, and ANR project Multimod (ANR-17-CE22-0016), ANR-17-CE40-0015,DISTANCIA,Théorie métrique des graphes(2017), ANR-17-CE22-0016,MultiMod,Scalable routing in Multi-Modal transportation networks(2017), Université de Paris (UP), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), ANR-17-CE22-0016,MultiMod,Routage dans les grands réseaux de transports multi-modal(2017), Viennot, Laurent, Théorie métrique des graphes - - DISTANCIA2017 - ANR-17-CE40-0015 - AAPG2017 - VALID, Routage dans les grands réseaux de transports multi-modal - - MultiMod2017 - ANR-17-CE22-0016 - AAPG2017 - VALID, University of Bucharest (UniBuc), National Institute for Research and Development in Informatics [Bucharest] (ICI), Guillaume Ducoffe's work was supported by a grant of Romanian Ministry of Research and Innovation CCCDI-UEFISCDI. projectno. 17PCCDI/2018. Michel Habib was supported by Inria Gang project-team, and ANR project DISTANCIA (ANR-17-CE40-0015). Laurent Viennot was supported by Irif laboratory from CNRS and Paris University, and ANR project Multimod (ANR-17-CE22-0016)., Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), and Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: FOS: Computer and information sciences, Hypergraph, General Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Order (ring theory), [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Clique (graph theory), Theoretical Computer Science, Treewidth, Combinatorics, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Independent set, Computer Science - Data Structures and Algorithms, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Discrete Mathematics and Combinatorics, Interval (graph theory), Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), Split graph, Combinatorics (math.CO), Time complexity, Mathematics
Abstract: When can we compute the diameter of a graph in quasi linear time? We address this question for the class of {\em split graphs}, that we observe to be the hardest instances for deciding whether the diameter is at most two. We stress that although the diameter of a non-complete split graph can only be either $2$ or $3$, under the Strong Exponential-Time Hypothesis (SETH) we cannot compute the diameter of an $n$-vertex $m$-edge split graph in less than quadratic time -- in the size $n+m$ of the input. Therefore it is worth to study the complexity of diameter computation on {\em subclasses} of split graphs, in order to better understand the complexity border. Specifically, we consider the split graphs with bounded {\em clique-interval number} and their complements, with the former being a natural variation of the concept of interval number for split graphs that we introduce in this paper. We first discuss the relations between the clique-interval number and other graph invariants such as the classic interval number of graphs, the treewidth, the {\em VC-dimension} and the {\em stabbing number} of a related hypergraph. Then, in part based on these above relations, we almost completely settle the complexity of diameter computation on these subclasses of split graphs: - For the $k$-clique-interval split graphs, we can compute their diameter in truly subquadratic time if $k={\cal O}(1)$, and even in quasi linear time if $k=o(\log{n})$ and in addition a corresponding ordering of the vertices in the clique is given. However, under SETH this cannot be done in truly subquadratic time for any $k = \omega(\log{n})$. - For the {\em complements} of $k$-clique-interval split graphs, we can compute their diameter in truly subquadratic time if $k={\cal O}(1)$, and even in time ${\cal O}(km)$ if a corresponding ordering of the vertices in the stable set is given. Again this latter result is optimal under SETH up to polylogarithmic factors. Our findings raise the question whether a $k$-clique interval ordering can always be computed in quasi linear time. We prove that it is the case for $k=1$ and for some subclasses such as bounded-treewidth split graphs, threshold graphs and comparability split graphs. Finally, we prove that some important subclasses of split graphs -- including the ones mentioned above -- have a bounded clique-interval number.
Published: 2019

16. Théorie algorithmique des jeux appliquée aux réseaux et aux populations

Author: Collet, Simon, 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), Université Paris 7 - Diderot, Pierre Fraigniaud, Amos Korman, and Université de Paris
Subjects: Behavior, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Equilibrium, Evolution, Calcul distribué, Stratégie évolutivement stable (SES), Population, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Strategy, Game, Network, Complexity, Distributed computing, Théorie des jeux, Algorithm, Information, Jeux en réseau, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Game theory
Abstract: The aim of this thesis is to use algorithmic game theory tools to study various games inspired from real world problems in the fields of information networks and biology. These games are characterized by a large number of players, each with incomplete information about other players. In classical game theory, these games fall into the category of extensive games with imperfect information, which are modeled using trees. However, these games remain very difficult to analyze in details, because of their intrinsic complexity, which is linked with their possibly infinite tree depth. Nevertheless, we have taken up the challenge of this task, while diversifying the methods of resolution, and emphasizing its interdisciplinary aspect.Besides the introduction and the conclusion, the thesis is divided into three parts. In the first part, we adopt the point of view of classical game theory. We propose a game that corresponds to a wide class of problems encountered in the theory of distributed computing. The main contributions of this part are, on the one hand, to show how to transform a purely algorithmic problem into a game, and, on the other hand, to prove the existence of satisfactory equilibria for the resulting class of games. This second point is essential, as it guarantees that game theory is adapted to the study of distributed games, despite their complexity. The second part is dedicated to the study of a game omnipresent within biological systems, that we call dispersion game. This game models the situation in which a group of animals must share a certain amount of resources scattered among different geographical sites. The difficulty of the game comes from the fact that some sites contain more resources than others, but may also attract more players. We propose a rule for the distribution of resources which makes it possible to maximize the resources exploited by the whole group. This part of the thesis is also an opportunity to revisit the close links between the concept of ideal free distribution, very present in the theory of foraging, and the concept of evolutionarily stable strategy, a key concept of evolutionary game theory. The third part focuses on the study of the behavior of a specific species of small bats living in Mexico, in the Sonoran Desert, and feeding at night from the nectar of the giant Saguaro cacti, a protected species. After the presentation of the experimental results obtained in the field, we propose a computer simulation of their behavior. The results of these simulations make it possible to formulate interesting hypotheses about the cerebral activities of these small mammals. We then study a theoretical model of game inspired by this real situation. The study of this abstract model allows us to distinguish the fundamental characteristics of the game, and to reinforce our approach of theorizing foraging behavior. This study also opens the way to applying this type of model to other situations, involving animal or human behavior.; Cette thèse se propose d’étudier, sous l’angle de la théorie algorithmique des jeux, divers jeux inspirés de situations réelles rencontrées dans les domaines des réseaux informatiques et de la biologie. Ces jeux se caractérisent par un grand nombre de joueurs disposant chacun d’une information incomplète à propos des autres joueurs. Dans la théorie classique, ces jeux rentrent dans la catégorie des jeux extensifs à information imparfaite et sont modélisés à l'aide d'arbres. Ils restent toutefois très difficiles à analyser en détail, à cause de leur inhérente complexité, liée notamment à une profondeur d’arbre potentiellement infinie. Nous avons relevé le défi de cette tâche en diversifiant les méthodes de résolution et en mettant l’accent sur son aspect interdisciplinaire.Cette thèse, outre l’introduction et la conclusion, se divise en trois parties. Dans la première, nous adoptons le point de vue de la théorie des jeux classique. Nous proposons un modèle de jeu qui correspond à une large classe de problèmes rencontrés dans la théorie du calcul distribué. Les principales contributions de cette partie sont, d’une part, de montrer comment passer d’un point de vue purement algorithmique du problème à un point de vue correspondant à la théorie des jeux, et, d’autre part, de prouver l’existence d’équilibres satisfaisants pour la classe de jeux obtenue. Ce deuxième point est essentiel et garantit que la théorie des jeux est adaptée à l’étude de tels jeux distribués, malgré leur complexité.La seconde partie est consacrée à l’étude d’un jeu omniprésent au sein des systèmes biologiques que l’on nomme jeu de la dispersion. Il modélise la situation dans laquelle un groupe d’animaux doit se partager une certaine quantité de ressources répartie entre différents sites géographiques. La difficulté du jeu provient du fait que certains sites contiennent plus de ressources que d’autres, mais risquent également d’attirer plus de joueurs. Le partage est alors difficile. Nous proposons une règle de répartition des ressources qui permet de maximiser les ressources exploitées par l’ensemble du groupe. Cette partie est aussi l’occasion de revisiter les liens étroits entre le concept de distribution libre idéale, très présente dans la théorie du fourrageage, et le concept de stratégie évolutionnairement stable, concept clé de la théorie des jeux évolutionnaires.La troisième partie se concentre sur l’étude du comportement d’une certaine espèce de petites chauve-souris vivant au Mexique, dans le désert de Sonora, et se nourrissant la nuit du nectar des cactus géant de l’espèce protégée Saguaro. Après la présentation des résultats expérimentaux obtenus sur le terrain, nous proposons une simulation informatique de leur comportement. Les résultats de ces simulations permettent de formuler des hypothèses intéressantes à propos du fonctionnement cérébral de ces petits mammifères. Nous étudions ensuite un modèle théorique de jeu inspiré de cette situation réelle. L’étude de ce modèle abstrait nous permet de distinguer les caractéristiques fondamentales du jeu, et de renforcer notre approche de théorisation du comportement de fourrageage. Cette étude ouvre également la voie à l’application de ce type de modèle à d’autres situations, impliquant un comportement animal ou humain.
Published: 2019

17. Randomized proof-labeling schemes

Author: Boaz Patt-Shamir, Mor Baruch, Pierre Fraigniaud, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Tel Aviv University (TAU), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), 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 Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), 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, Department of Electrical Engineering, and Tel Aviv University [Tel Aviv]
Subjects: Scheme (programming language), Correctness, Theoretical computer science, Proof-labeling schemes, Computer Networks and Communications, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Upper and lower bounds, Non-determinism, Theoretical Computer Science, 0202 electrical engineering, electronic engineering, information engineering, Communication complexity, ComputingMilieux_MISCELLANEOUS, computer.programming_language, Randomized algorithms, Probabilistic logic, Distributed verification, 020206 networking & telecommunications, Predicate (mathematical logic), Randomized algorithm, Computational Theory and Mathematics, 010201 computation theory & mathematics, Hardware and Architecture, Distributed algorithm, Theory of computation, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], computer, Algorithm
Abstract: International audience; A proof-labeling scheme, introduced by Korman, Kutten and Peleg [PODC 2005], is a mechanism enabling to certify the legality of a network configuration with respect to a boolean predicate. Such a mechanism finds applications in many frameworks, including the design of fault-tolerant distributed algorithms. In a proof-labeling scheme, the verification phase consists of exchanging labels between neighbors. The size of these labels depends on the network predicate to be checked. There are predicates requiring large labels, of poly-logarithmic size (e.g., MST), or even polynomial size (e.g., Symmetry). In this paper, we introduce the notion of randomized proof-labeling schemes. By reduction from deterministic schemes, we show that randomization enables the amount of communication to be exponentially reduced. As a consequence, we show that checking any network predicate can be done with probability of correctness as close to one as desired by exchanging just a logarithmic number of bits between neighbors. Moreover, we design a novel space lower bound technique that applies to both deterministic and randomized proof-labeling schemes. Using this technique, we establish several tight bounds on the verification complexity of classical distributed computing problems, such as MST construction, and of classical predicates such as acyclicity, connectivity, and cycle length.
Published: 2018

18. Brief Announcement: Distributed Computing in the Asynchronous {LOCAL} Model

Author: Pierre Fraigniaud, Hugues Fauconnier, Mikaël Rabie, Carole Delporte-Gallet, 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), and This research is supported by the ANR project DESCARTES (ref. DS0702-2016). Additional support from the INRIA project GANG.
Subjects: Discrete mathematics, TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES, Deterministic algorithm, Computer science, [SCCO.COMP]Cognitive science/Computer science, 0102 computer and information sciences, 02 engineering and technology, Computer Science::Computational Complexity, 01 natural sciences, Task (project management), TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, 010201 computation theory & mathematics, Asynchronous communication, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, ComputingMilieux_MISCELLANEOUS, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; We show that, for any task T associated to a locally checkable labeling (lcl), if T is solvable in t rounds by a deterministic algorithm in the local model, then T remains solvable by a deterministic algorithm in O(t) rounds in an asynchronous variant of the local model whenever t=O(polylogn).
Published: 2019

19. Synchronous t-Resilient Consensus in Arbitrary Graphs

Author: Armando Castañeda, Pierre Fraigniaud, Matthieu Roy, Sergio Rajsbaum, Ami Paz, Corentin Travers, Technion - Israel Institute of Technology [Haifa], Networks, Graphs and Algorithms (GANG), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), 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), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Instituto de Matematicas [México], Universidad Nacional Autónoma de México (UNAM), Équipe Tolérance aux fautes et Sûreté de Fonctionnement informatique (LAAS-TSF), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Universidad Politécnica de Madrid (UPM), Supported by ANR Project DESCARTES, INRIA Project GANG, UNAM-PAPIIT IA102417 and IN109917, and Fondation des Sciences Mathématiques de Paris., ANR-16-CE40-0023,DESCARTES,Abstraction modulaire pour le calcul distribué(2016), Universidad Nacional Autónoma de México = National Autonomous University of Mexico (UNAM), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Institut National Polytechnique (Toulouse) (Toulouse INP), and Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)
Subjects: Discrete mathematics, Consensus, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Complete graph, Crash, Combinatorial topology, 0102 computer and information sciences, 02 engineering and technology, Radius, 01 natural sciences, Upper and lower bounds, Computer Science Applications, Theoretical Computer Science, Synchronous network, Computational Theory and Mathematics, 010201 computation theory & mathematics, Distributed graph algorithms, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Crash failures, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Information Systems
Abstract: Best Paper Award; International audience; We study the number of rounds needed to solve consensus in a synchronous network G where at most t nodes may fail by crashing. This problem has been thoroughly studied when G is a complete graph, but very little is known when G is arbitrary. We define a notion of radius that considers all ways in which t nodes may crash, and present an algorithm that solves consensus in radius rounds. Then we derive a lower bound showing that our algorithm is optimal for vertex-transitive graphs, among oblivious algorithms.
Published: 2019

20. A Comparative Study of Neural Network Compression

Author: Baktash, Hossein, Natale, Emanuele, Viennot, Laurent, Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria), Sharif University of Technology [Tehran] (SUT), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria 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), Networks, Graphs and Algorithms (GANG), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), 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, INRIA Sophia Antipolis - I3S, 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), Université Nice Sophia Antipolis (1965 - 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 (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)
Subjects: [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG]
Abstract: There has recently been an increasing desire to evaluate neural networks locally on computationally-limited devices in order to exploit their recent effectiveness for several applications; such effectiveness has nevertheless come together with a considerable increase in the size of modern neural networks, which constitute a major downside in several of the aforementioned computationally-limited settings. There has thus been a demand of compression techniques for neural networks. Several proposal in this direction have been made, which famously include hashing-based methods and pruning-based ones. However, the evaluation of the efficacy of these techniques has so far been heterogeneous, with no clear evidence in favor of any of them over the others. The goal of this work is to address this latter issue by providing a comparative study. While most previous studies test the capability of a technique in reducing the number of parameters of state-of-the-art networks , we follow [CWT + 15] in evaluating their performance on basic ar-chitectures on the MNIST dataset and variants of it, which allows for a clearer analysis of some aspects of their behavior. To the best of our knowledge, we are the first to directly compare famous approaches such as HashedNet, Optimal Brain Damage (OBD), and magnitude-based pruning with L1 and L2 regularization among them and against equivalent-size feed-forward neural networks with simple (fully-connected) and structural (convolutional) neural networks. Rather surprisingly, our experiments show that (iterative) pruning-based methods are substantially better than the HashedNet architecture, whose compression doesn't appear advantageous to a carefully chosen convolutional network. We also show that, when the compression level is high, the famous OBD pruning heuristics deteriorates to the point of being less efficient than simple magnitude-based techniques.
Published: 2019

21. Participant-Restricted Consensus in Asynchronous Crash-Prone Read/Write Systems and Its Weakest Failure Detector

Author: Michel Raynal, Hugues Fauconnier, Carole Delporte-Gallet, 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), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), The Hong Kong Polytechnic University [Hong Kong] (POLYU), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), and Delporte-Gallet, Carole
Subjects: 050101 languages & linguistics, Asynchronous system, Computer science, Concurrency, 05 social sciences, Detector, [SCCO.COMP]Cognitive science/Computer science, Crash, 02 engineering and technology, Object (computer science), Computer engineering, [SCCO.COMP] Cognitive science/Computer science, Asynchronous communication, Models of communication, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, 0501 psychology and cognitive sciences, Failure detector, ComputingMilieux_MISCELLANEOUS
Abstract: A failure detector is a device (object) that provides the processes with information on failures. Failure detectors were introduced to enrich asynchronous systems so that it becomes possible to solve problems (or implement concurrent objects) that are otherwise impossible to solve in pure asynchronous systems where processes are prone to crash failures. The most famous failure detector (which is called “eventual leader” and denoted $\varOmega $) is the weakest failure detector which allows consensus to be solved in n-process asynchronous systems where up to $t=n-1$ processes may crash in the read/write communication model, and up to \(t
Published: 2019

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

23. On the Minimum Eccentricity Isometric Cycle Problem

Author: Léo Planche, Etienne Birmelé, Fabien de Montgolfier, Mathématiques Appliquées Paris 5 (MAP5 - UMR 8145), Université Paris Descartes - Paris 5 (UPD5)-Institut National des Sciences Mathématiques et de leurs Interactions (INSMI)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), 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), and Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)
Subjects: General Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Isometric exercise, k-domination, k-covering, 01 natural sciences, Graph, Isometric cycle, Theoretical Computer Science, Eccentricity, Combinatorics, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, Astrophysics::Earth and Planetary Astrophysics, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics
Abstract: International audience; In this paper we investigate the Minimum Eccentricity Isometric Cycle (MEIC) problem. Given a graph, this problem consists in finding an isometric cycle with smallest possible eccentricity k. We show that this problem is NP-Hard and we propose a 3-approximation algorithm running in O(n(m + kn)) time.
Published: 2019

24. A General Algorithmic Scheme for Modular Decompositions of Hypergraphs and Applications

Author: Lalla Mouatadid, Fabien de Montgolfier, Mengchuan Zou, Michel Habib, 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), Department of Computer Science [University of Toronto] (DCS), and University of Toronto
Subjects: Discrete mathematics, Polynomial, business.industry, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, Modular design, 01 natural sciences, Modular decomposition, Orthogonality, 010201 computation theory & mathematics, Scheme (mathematics), 0202 electrical engineering, electronic engineering, information engineering, Decomposition (computer science), 020201 artificial intelligence & image processing, [INFO]Computer Science [cs], Focus (optics), business, Time complexity, ComputingMilieux_MISCELLANEOUS, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics
Abstract: We study here algorithmic aspects of modular decomposition of hypergraphs. In the literature one can find three different definitions of modules, namely: the standard one [19], the k-subset modules [6] and the Courcelle’s one [11]. Using the fundamental tools defined for combinatorial decompositions such as partitive and orthogonal families, we directly derive a linear time algorithm for Courcelle’s decomposition. Then we introduce a general algorithmic tool for partitive families and apply it for the other two definitions of modules to derive polynomial algorithms. For standard modules it leads to an algorithm in $O(n^3 \cdot l)$ time (where n is the number of vertices and l is the sum of the size of the edges). For k-subset modules we obtain $O(n^3\cdot m\cdot l)$ (where m is the number of edges). This is an improvement from the best known algorithms for k-subset modular decomposition, which was not polynomial w.r.t. n and m, and is in $O(n^{3k-5})$ time [6] where k denotes the maximal size of an edge. Finally we focus on applications of orthogonality to modular decompositions of tournaments, simplifying the algorithm from [18]. The question of designing a linear time algorithms for the standard modular decomposition of hypergraphs remains open.
Published: 2019

25. A Topological Perspective on Distributed Network Algorithms

Author: Ami Paz, Matthieu Roy, Sergio Rajsbaum, Pierre Fraigniaud, Armando Castañeda, Corentin Travers, Technion - Israel Institute of Technology [Haifa], 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), Instituto de Matematicas [México], Universidad Nacional Autónoma de México (UNAM), Équipe Tolérance aux fautes et Sûreté de Fonctionnement informatique (LAAS-TSF), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, 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), Pierre Fraigniaud and Corentin Travers are supported by ANR projects DESCARTES and FREDA, Pierre Fraigniaud receives additional support from INRIA project GANG, Ami Paz is supported by the Fondation Sciences Mathématiques de Paris (FSMP), Sergio Rajsbaum is supported by project unam-papiit IN109917., Keren Censor-Hillel, Michele Flammini, ANR-16-CE40-0023,DESCARTES,Abstraction modulaire pour le calcul distribué(2016), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Universidad Nacional Autónoma de México = National Autonomous University of Mexico (UNAM), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J), and 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-Université Bordeaux Segalen - Bordeaux 2
Subjects: FOS: Computer and information sciences, Network algorithms, General Computer Science, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Structure (category theory), Combinatorial topology, 0102 computer and information sciences, 02 engineering and technology, Topology, 01 natural sciences, Theoretical Computer Science, 0202 electrical engineering, electronic engineering, information engineering, ComputingMilieux_MISCELLANEOUS, Message passing, Perspective (graphical), 020207 software engineering, 16. Peace & justice, Distributed computing, Shared memory, Computer Science - Distributed, Parallel, and Cluster Computing, Distributed algorithm, 010201 computation theory & mathematics, Distributed graph algorithms, 020201 artificial intelligence & image processing, Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: International audience; More than two decades ago, combinatorial topology was shown to be useful for analyzing distributed fault-tolerant algorithms in shared memory systems and in message passing systems. In this work, we show that combinatorial topology can also be useful for analyzing distributed algorithms in networks of arbitrary structure. To illustrate this, we analyze consensus, set-agreement, and approximate agreement in networks, and derive lower bounds for these problems under classical computational settings, such as the LOCAL model and dynamic networks.
Published: 2019

26. When an optimal dominating set with given constraints exists

Author: Narges Ghareghani, Mohammad Reza Hooshmandasl, Reza Naserasr, Omid Etesami, Pouyeh Sharifani, Michel Habib, Institute for Research in Fundamental Sciences [Tehran] (IPM), 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), Yazd University, The research of the second author was in part supported by the grant 96050016 from IPM and the research of the third and fifth author was supported by grant number ANR-17-CE40-0022., ANR-17-CE40-0022,HOSIGRA,Homomorphismes de graphes signés(2017), and Institute for Research in Fundamental Sciences (IPM)
Subjects: General Computer Science, Total dominating set, Comparability, Permutation graphs, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Graph, Theoretical Computer Science, Vertex (geometry), Combinatorics, Dominating set, 010201 computation theory & mathematics, Chordal graph, Bounded function, 0202 electrical engineering, electronic engineering, information engineering, NP-hardness, Interval graphs, 020201 artificial intelligence & image processing, [INFO]Computer Science [cs], Mathematics
Abstract: A dominating set is a set S of vertices in a graph such that every vertex not in S is adjacent to a vertex in S. In this paper, we consider the set of all optimal (i.e. smallest) dominating sets S, and ask of the existence of at least one such set S with given constraints. The constraints say that the number of neighbors in S of a vertex inside S must be in a given set ρ, and the number of neighbors of a vertex outside S must be in a given set σ. For example, if ρ is [ 1 , k ] , and σ is the nonnegative integers, this corresponds to “ [ 1 , k ] -domination.” First, we consider the complexity of recognizing whether an optimal dominating set with given constraints exists or not. We show via two different reductions that this problem is NP-hard for certain given constraints. This, in particular, answers a question of [M. Chellali et al., [ 1 , 2 ] -dominating sets in graphs, Discrete Applied Mathematics 161 (2013) 2885–2893] regarding the constraint that the number of neighbors in the set be upper-bounded by 2. We also consider the corresponding question regarding “total” dominating sets. Next, we consider some well-structured classes of graphs, including permutation and interval graphs (and their subfamilies), and determine exactly the smallest k such that for all graphs in that family an optimal dominating set exists where every vertex is dominated at most k times. We also consider the problem for trees (with implications for chordal and comparability graphs) and graphs with bounded “asteroidal number”.
Published: 2019

27. Towards Synthesis of Distributed Algorithms with {SMT} Solvers

Author: Carole Delporte-Gallet, Yan Jurski, Arnaud Sangnier, François Laroussinie, Hugues Fauconnier, 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), and Delporte-Gallet, Carole
Subjects: Correctness, Computer science, [SCCO.COMP]Cognitive science/Computer science, 020207 software engineering, Context (language use), 0102 computer and information sciences, 02 engineering and technology, Parallel computing, 01 natural sciences, [SCCO.COMP] Cognitive science/Computer science, 010201 computation theory & mathematics, Distributed algorithm, Satisfiability modulo theories, 0202 electrical engineering, electronic engineering, information engineering, Temporal logic, Finite state, Time complexity, ComputingMilieux_MISCELLANEOUS
Abstract: We consider the problem of synthesizing distributed algorithms working on a specific execution context. We show it is possible to use the linear time temporal logic in order to both specify the correctness of algorithms and their execution contexts. We then provide a method allowing to reduce the synthesis problem of finite state algorithms to some model-checking problems. We finally apply our technique to automatically generate algorithms for consensus and epsilon-agreement in the case of two processes using the SMT solver Z3.
Published: 2019

28. Making Local Algorithms Wait-Free: the Case of Ring Coloring

Author: Castañeda, Armando, Delporte-Gallet, Carole, Fauconnier, Hugues, Rajsbaum, Sergio, Raynal, Michel, Instituto de Matematicas [México], Universidad Nacional Autónoma de México (UNAM), 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), 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.), the World Is Distributed Exploring the tension between scale and coordination (WIDE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), C. Delporte, H. Fauconnier, and M. Raynal, were partially supported by the French ANR project DESCARTES, devoted to abstraction layers in distributed computing. A. Castaneda was supported in part by UNAM PAPIIT-DGAPA projects IA101015 and IA102417. S. Rajsbaum was supported in part by UNAM PAPIIT-DGAPA project IN107714.All the authors want to thank INRIA for its support in the context of the INRIA-UNAM ' ́Equipe Associée' LiDiCo (At the Limits of DistributedComputing)., Universidad Nacional Autónoma de México = National Autonomous University of Mexico (UNAM), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), and Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique)
Subjects: Algorithm, Locality of a computation, Cole and Vishkin's coloring, Wait-freedom, Process crash failure, Vertex coloring problem, [SCCO.COMP]Cognitive science/Computer science, Synchronous distributed computing, Message-passing, Synchronous communication
Abstract: International audience; When considering distributed computing, reliable message-passing synchronous systems on the one side, and asynchronous failure-prone shared-memory systems on the other side, remain two quite independently studied ends of the relia-bility/asynchrony spectrum. The concept of locality of a computation is central to the first one, while the concept of wait-freedom is central to the second one. The paper proposes a new DECOUPLED model in an attempt to reconcile these two worlds. It consists of a synchronous and reliable communication graph of n nodes, and on top a set of asynchronous crash-prone processes, each attached to a communication node. To illustrate the DECOUPLED model, the paper presents an asynchronous 3-coloring algorithm for the processes of a ring. From the processes point of view, the This article is part Theory Comput Syst algorithm is wait-free. From a locality point of view, each process uses information only from processes at distance O(log * n) from it. This local wait-free algorithm is based on an extension of the classical Cole and Vishkin's vertex coloring algorithm in which the processes are not required to start simultaneously.
Published: 2019

29. Independent Lazy Better-Response Dynamics on Network Games

Author: Paolo Penna, Laurent Viennot, Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich] (ETH Zürich), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratory of Information, Network and Communication Sciences (LINCS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT)-Sorbonne Université (SU), 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), ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), and Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology in Zürich [Zürich] (ETH Zürich)
Subjects: TheoryofComputation_MISCELLANEOUS, FOS: Computer and information sciences, Computer Science::Computer Science and Game Theory, Theoretical computer science, Computer science, 0102 computer and information sciences, Machine learning, computer.software_genre, 01 natural sciences, [INFO.INFO-SI]Computer Science [cs]/Social and Information Networks [cs.SI], symbols.namesake, Computer Science - Computer Science and Game Theory, 0502 economics and business, Convergence (routing), 050207 economics, Social and Information Networks (cs.SI), Network games, Degree (graph theory), [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], business.industry, 05 social sciences, ComputingMilieux_PERSONALCOMPUTING, Computer Science - Social and Information Networks, Function (mathematics), Independent dynamics, Network formation, 010201 computation theory & mathematics, Dynamics (music), Distributed algorithm, Nash equilibrium, symbols, Artificial intelligence, Algorithmic game theory, business, computer, Computer Science and Game Theory (cs.GT)
Abstract: International audience; We study an independent best-response dynamics on network games in which the nodes (players) decide to revise their strategies independently with some probability. We provide several bounds on the convergence time to an equilibrium as a function of this probability, the degree of the network, and the potential of the underlying games. These dynamics are somewhat more suitable for distributed environments than the classical better- and best-response dynamics where players revise their strategies "sequentially'", i.e., no two players revise their strategies simultaneously.
Published: 2019

30. About Some Hereditary Classes of Graphs : Algorithms - Structure - Coloration

Author: Charbit, Pierre, 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), Université Paris Diderot, Pierre Fraigniaud, and Charbit, Pierre
Subjects: [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Théorie des Graphes - Algorithmique des Graphes - Coloriage de Graphes, [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], Graph Theory - Graph Algorithms - Graph Colouring, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]
Published: 2019

31. On the Weakest Failure Detector for Read/Write-Based Mutual Exclusion

Author: Michel Raynal, Hugues Fauconnier, Carole Delporte-Gallet, 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), The Hong Kong Polytechnic University [Hong Kong] (POLYU), the World Is Distributed Exploring the tension between scale and coordination (WIDE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique)
Subjects: Computer engineering, 010201 computation theory & mathematics, Asynchronous communication, Computer science, 0202 electrical engineering, electronic engineering, information engineering, [SCCO.COMP]Cognitive science/Computer science, 020201 artificial intelligence & image processing, 0102 computer and information sciences, 02 engineering and technology, Failure detector, Mutual exclusion, 01 natural sciences, ComputingMilieux_MISCELLANEOUS
Abstract: Failure detectors are devices (objects) that provides the processes with information on failures. They were introduced to enrich asynchronous systems so that it becomes possible to solve problems (or implement concurrent objects) that are otherwise impossible to solve in pure asynchronous systems where processes are prone to crash failures. The most famous failure detector (which is called “eventual leader” and denoted $\varOmega $) is the weakest failure detector which allows consensus to be solved in n-process asynchronous systems where up to $t=n-1$ processes may crash in the read/write communication model, and up to \(t
Published: 2019

32. A Comparative Study of Neural Network Compression

Author: Baktash, Hossein, Natale, Emanuele, Viennot, Laurent, Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria), Sharif University of Technology [Tehran] (SUT), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), 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), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Nice Sophia Antipolis (... - 2019) (UNS), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-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), Networks, Graphs and Algorithms (GANG), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), and 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
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Statistics - Machine Learning, Machine Learning (stat.ML), Machine Learning (cs.LG)
Abstract: There has recently been an increasing desire to evaluate neural networks locally on computationally-limited devices in order to exploit their recent effectiveness for several applications; such effectiveness has nevertheless come together with a considerable increase in the size of modern neural networks, which constitute a major downside in several of the aforementioned computationally-limited settings. There has thus been a demand of compression techniques for neural networks. Several proposal in this direction have been made, which famously include hashing-based methods and pruning-based ones. However, the evaluation of the efficacy of these techniques has so far been heterogeneous, with no clear evidence in favor of any of them over the others. The goal of this work is to address this latter issue by providing a comparative study. While most previous studies test the capability of a technique in reducing the number of parameters of state-of-the-art networks , we follow [CWT + 15] in evaluating their performance on basic ar-chitectures on the MNIST dataset and variants of it, which allows for a clearer analysis of some aspects of their behavior. To the best of our knowledge, we are the first to directly compare famous approaches such as HashedNet, Optimal Brain Damage (OBD), and magnitude-based pruning with L1 and L2 regularization among them and against equivalent-size feed-forward neural networks with simple (fully-connected) and structural (convolutional) neural networks. Rather surprisingly, our experiments show that (iterative) pruning-based methods are substantially better than the HashedNet architecture, whose compression doesn't appear advantageous to a carefully chosen convolutional network. We also show that, when the compression level is high, the famous OBD pruning heuristics deteriorates to the point of being less efficient than simple magnitude-based techniques.
Published: 2019
Full Text: View/download PDF

33. Multi-Round Cooperative Search Games with Multiple Players

Author: Yoav Rodeh, Amos Korman, Wagner, Michael, Networks, Graphs and Algorithms (GANG), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), 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), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Weizmann Institute of Science [Rehovot, Israël], This work has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (grant agreement No 648032), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), ORT Braude College [Karmiel, Israel], Weizmann Institute of Science, Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), and Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)
Subjects: FOS: Computer and information sciences, TheoryofComputation_MISCELLANEOUS, 0106 biological sciences, Distribution (number theory), Computer Networks and Communications, ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, 0102 computer and information sciences, 010603 evolutionary biology, 01 natural sciences, Theoretical Computer Science, Computer Science - Computer Science and Game Theory, Price of anarchy, Fraction (mathematics), Group performance, Mathematics, Focus (computing), 000 Computer science, knowledge, general works, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Applied Mathematics, TheoryofComputation_GENERAL, Computer Science - Distributed, Parallel, and Cluster Computing, Computational Theory and Mathematics, 010201 computation theory & mathematics, Computer Science, Distributed, Parallel, and Cluster Computing (cs.DC), Treasure, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Mathematical economics, Computer Science and Game Theory (cs.GT)
Abstract: International audience; Assume that a treasure is placed in one of M boxes according to a known distribution and that k searchers are searching for it in parallel during T rounds. We study the question of how to incentivize selfish players so that group performance would be maximized. Here, this is measured by the success probability, namely, the probability that at least one player finds the treasure. We focus on congestion policies C() that specify the reward that a player receives if it is one of players that (simultaneously) find the treasure for the first time. Our main technical contribution is proving that the exclusive policy, in which C(1) = 1 and C() = 0 for > 1, yields a price of anarchy of (1 − (1 − 1/k) k) −1 , and that this is the best possible price among all symmetric reward mechanisms. For this policy we also have an explicit description of a symmetric equilibrium, which is in some sense unique, and moreover enjoys the best success probability among all symmetric profiles. For general congestion policies, we show how to polynomially find, for any θ > 0, a symmetric multiplicative (1 + θ)(1 + C(k))-equilibrium. Together with an appropriate reward policy, a central entity can suggest players to play a particular profile at equilibrium. As our main conceptual contribution, we advocate the use of symmetric equilibria for such purposes. Besides being fair, we argue that symmetric equilibria can also become highly robust to crashes of players. Indeed, in many cases, despite the fact that some small fraction of players crash (or refuse to participate), symmetric equilibria remain efficient in terms of their group performances and, at the same time, serve as approximate equilibria. We show that this principle holds for a class of games, which we call monotonously scalable games. This applies in particular to our search game, assuming the natural sharing policy, in which C() = 1//. For the exclusive policy, this general result does not hold, but we show that the symmetric equilibrium is nevertheless robust under mild assumptions.
Published: 2019

34. Fast Public Transit Routing with Unrestricted Walking Through Hub Labeling

Author: Duc-Minh Phan, Laurent Viennot, Got It Vietnam, Networks, Graphs and Algorithms (GANG), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), 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), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratory of Information, Network and Communication Sciences (LINCS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT)-Sorbonne Université (SU), Université Paris Diderot - Paris 7 (UPD7), ANR-17-CE22-0016,MultiMod,Routage dans les grands réseaux de transports multi-modal(2017), and ANR-17-CE22-0016,MultiMod,Scalable routing in Multi-Modal transportation networks(2017)
Subjects: FOS: Computer and information sciences, Speedup, Computer science, Public transportation, 02 engineering and technology, Interval (mathematics), Route planning, Arrival time, Computer Science - Networking and Internet Architecture, Hub labeling, Contraction hierarchies, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Computer Science - Data Structures and Algorithms, 0502 economics and business, 11. Sustainability, 0202 electrical engineering, electronic engineering, information engineering, Data Structures and Algorithms (cs.DS), Networking and Internet Architecture (cs.NI), 050210 logistics & transportation, business.industry, 05 social sciences, Walking time, Travel time, Public transport, 020201 artificial intelligence & image processing, Routing (electronic design automation), business, Computer network
Abstract: We propose a novel technique for answering routing queries in public transportation networks that allows unrestricted walking. We consider several types of queries: earliest arrival time, Pareto-optimal journeys regarding arrival time, number of transfers and walking time, and profile, i.e. finding all Pareto-optimal journeys regarding travel time and arrival time in a given time interval. Our techniques uses hub labeling to represent unlimited foot transfers and can be adapted to both classical algorithms RAPTOR and CSA. We obtain significant speedup compared to the state-of-the-art approach based on contraction hierarchies. A research report version is deposited on HAL with number hal-02161283.
Published: 2019

35. Special Issue on NETYS 2016, Computing (journal)

Author: Delporte-Gallet, Carole, Abdulla, Parosh, 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), and Uppsala University
Subjects: [SCCO.COMP]Cognitive science/Computer science, ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2019

36. Diameter computation on $H$-minor free graphs and graphs of bounded (distance) VC-dimension

Author: Guillaume Ducoffe, Michel Habib, Laurent Viennot, National Institute for Research and Development in Informatics [Bucharest] (ICI), University of Bucharest (UniBuc), Université Paris Cité (UPCité), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Networks, Graphs and Algorithms (GANG), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), This work was supported by project PN 19 37 04 01 'New solutions for complex problems in current ICT researchfields based on modelling and optimization', funded by the Romanian Core Program of the Ministry of Researchand Innovation (MCI) 2019-2022. This work was also supported by a grant of Romanian Ministry of Research andInnovation CCCDI-UEFISCDI. project no. 17PCCDI/2018., ANR-17-CE40-0015,DISTANCIA,Théorie métrique des graphes(2017), ANR-17-CE22-0016,MultiMod,Routage dans les grands réseaux de transports multi-modal(2017), University of Bucharest, Faculty of Mathematics and Computer Science, National Institute for Research and Development in Informatics [Bucharest], Université de Paris, 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)-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), ANR-17-CE22-0016,MultiMod,Scalable routing in Multi-Modal transportation networks(2017), Université de Paris (UP), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), and Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)
Subjects: FOS: Computer and information sciences, 010201 computation theory & mathematics, Computer Science - Data Structures and Algorithms, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Data Structures and Algorithms (cs.DS), 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences
Abstract: We propose to study unweighted graphs of constant distance VC-dimension as a broad generalization of many graph classes for which we can compute the diameter in truly subquadratic-time. In particular for any fixed $H$, the class of $H$-minor free graphs has distance VC-dimension at most $|V(H)|-1$. Our first main result is that on graphs of distance VC-dimension at most $d$, for any fixed $k$ we can either compute the diameter or conclude that it is larger than $k$ in time $\tilde{\cal O}(k\cdot mn^{1-\varepsilon_d})$, where $\varepsilon_d \in (0;1)$ only depends on $d$. Then as a byproduct of our approach, we get the first truly subquadratic-time algorithm for constant diameter computation on all the nowhere dense graph classes. Finally, we show how to remove the dependency on $k$ for any graph class that excludes a fixed graph $H$ as a minor. More generally, our techniques apply to any graph with constant distance VC-dimension and polynomial expansion. As a result for all such graphs one obtains a truly subquadratic-time algorithm for computing their diameter. Our approach is based on the work of Chazelle and Welzl who proved the existence of spanning paths with strongly sublinear stabbing number for every hypergraph of constant VC-dimension. We show how to compute such paths efficiently by combining the best known approximation algorithms for the stabbing number problem with a clever use of $\varepsilon$-nets, region decomposition and other partition techniques., Comment: Submitted. Abstract shortened for the ArXiv listing
Published: 2019
Full Text: View/download PDF

37. Trade-Offs in Distributed Interactive Proofs

Author: Crescenzi, Pierluigi, Fraigniaud, Pierre, Paz, Ami, Fraigniaud, Pierre, 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, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: FOS: Computer and information sciences, Computer Science - Computational Complexity, 000 Computer science, knowledge, general works, Computer Science - Distributed, Parallel, and Cluster Computing, Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Distributed, Parallel, and Cluster Computing (cs.DC), Computational Complexity (cs.CC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], ComputingMilieux_MISCELLANEOUS
Abstract: The study of interactive proofs in the context of distributed network computing is a novel topic, recently introduced by Kol, Oshman, and Saxena [PODC 2018]. In the spirit of sequential interactive proofs theory, we study the power of distributed interactive proofs. This is achieved via a series of results establishing trade-offs between various parameters impacting the power of interactive proofs, including the number of interactions, the certificate size, the communication complexity, and the form of randomness used. Our results also connect distributed interactive proofs with the established field of distributed verification. In general, our results contribute to providing structure to the landscape of distributed interactive proofs., Comment: To be presented in DISC 2019
Published: 2019

38. Fast approximation of eccentricities and distances in hyperbolic graphs

Author: Hend Alrasheed, Michel Habib, Yann Vaxès, Victor Chepoi, Feodor F. Dragan, Algorithmique, Combinatoire et Recherche Opérationnelle (ACRO), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Kent State University, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), 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), The research of V.C., M.H., and Y.V. was supported by ANR project DISTANCIA (ANR-17-CE40-0015)., ANR-17-CE40-0015,DISTANCIA,Théorie métrique des graphes(2017), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), and Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)
Subjects: General Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, Monotonic function, 0102 computer and information sciences, 02 engineering and technology, [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, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO]Computer Science [cs], Time complexity, [MATH.MATH-MG]Mathematics [math]/Metric Geometry [math.MG], ComputingMilieux_MISCELLANEOUS, Mathematics, 021103 operations research, Shortest-path tree, Graph, Computer Science Applications, Vertex (geometry), Computational Theory and Mathematics, Distance matrix, 010201 computation theory & mathematics, Geometry and Topology, Centrality, Biological network
Abstract: International audience; We show that the eccentricities (and thus the centrality indices) of all vertices of a δ-hyperbolic graph G = (V, E) can be computed in linear time with an additive one-sided error of at most cδ, i.e., after a linear time preprocessing, for every vertex v of G one can compute in O(1) time an estimateê(v) of its eccentricity eccG(v) such that eccG(v) ≤ê(v) ≤ eccG(v) + cδ for a small constant c. We prove that every δ-hyperbolic graph G has a shortest path tree, constructible in linear time, such that for every vertex v of G, eccG(v) ≤ eccT (v) ≤ eccG(v) + cδ. These results are based on an interesting monotonicity property of the eccentricity function of hyperbolic graphs: the closer a vertex is to the center of G, the smaller its eccentricity is. We also show that the distance matrix of G with an additive one-sided error of at most c ′ δ can be computed in O(|V | 2 log 2 |V |) time, where c ′ < c is a small constant. Recent empirical studies show that many real-world graphs (including Internet application networks, web networks, collaboration networks, social networks, biological networks, and others) have small hyperbolicity. So, we analyze the performance of our algorithms for approximating centrality and distance matrix on a number of real-world networks. Our experimental results show that the obtained estimates are even better than the theoretical bounds.
Published: 2019

39. Equilibria of Games in Networks for Local Tasks

Author: Collet, Simon, Fraigniaud, Pierre, Penna, Paolo, 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), Cao, Jiannong, Ellen, Faith, Rodrigues, Luis, and Ferreira, Bernardo
Subjects: Network games, Locally checkable labelings, 000 Computer science, knowledge, general works, Algorithmic game theory, Computer Science, Local distributed computing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: Distributed tasks such as constructing a maximal independent set (MIS) in a network, or properly coloring the nodes or the edges of a network with reasonably few colors, are known to admit efficient distributed randomized algorithms. Those algorithms essentially proceed according to some simple generic rules, by letting each node choosing a temptative value at random, and checking whether this choice is consistent with the choices of the nodes in its vicinity. If this is the case, then the node outputs the chosen value, else it repeats the same process. Although such algorithms are, with high probability, running in a polylogarithmic number of rounds, they are not robust against actions performed by rational but selfish nodes. Indeed, such nodes may prefer specific individual outputs over others, e.g., because the formers suit better with some individual constraints. For instance, a node may prefer not being placed in a MIS as it is not willing to serve as a relay node. Similarly, a node may prefer not being assigned some radio frequencies (i.e., colors) as these frequencies would interfere with other devices running at that node. In this paper, we show that the probability distribution governing the choices of the output values in the generic algorithm can be tuned such that no nodes will rationally deviate from this distribution. More formally, and more generally, we prove that the large class of so-called LCL tasks, including MIS and coloring, admit simple "Luby's style" algorithms where the probability distribution governing the individual choices of the output values forms a Nash equilibrium. In fact, we establish the existence of a stronger form of equilibria, called symmetric trembling-hand perfect equilibria for those games., Leibniz International Proceedings in Informatics (LIPIcs), 125, ISSN:1868-8969, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018), ISBN:978-3-95977-098-9
Published: 2018

40. Graph classes and forbidden patterns on three vertices

Author: Laurent Feuilloley, Michel Habib, 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), ANR-17-CE40-0022,HOSIGRA,Homomorphismes de graphes signés(2017), Habib, Michel, and Homomorphismes de graphes signés - - HOSIGRA2017 - ANR-17-CE40-0022 - AAPG2017 - VALID
Subjects: Discrete mathematics, FOS: Computer and information sciences, Class (set theory), Discrete Mathematics (cs.DM), General Mathematics, [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, Characterization (mathematics), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Set (abstract data type), Combinatorics, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], 010201 computation theory & mathematics, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Graph (abstract data type), Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), Graph algorithms, Combinatorics (math.CO), MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics, Computer Science - Discrete Mathematics
Abstract: This paper deals with graph classes characterization and recognition. A popular way to characterize a graph class is to list a minimal set of forbidden induced subgraphs. Unfortunately this strategy usually does not lead to an efficient recognition algorithm. On the other hand, many graph classes can be efficiently recognized by techniques based on some interesting orderings of the nodes, such as the ones given by traversals. We study specifically graph classes that have an ordering avoiding some ordered structures. More precisely, we consider what we call patterns on three nodes, and the recognition complexity of the associated classes. In this domain, there are two key previous works. Damashke started the study of the classes defined by forbidden patterns, a set that contains interval, chordal and bipartite graphs among others. On the algorithmic side, Hell, Mohar and Rafiey proved that any class defined by a set of forbidden patterns can be recognized in polynomial time. We improve on these two works, by characterizing systematically all the classes defined sets of forbidden patterns (on three nodes), and proving that among the 23 different classes (up to complementation) that we find, 21 can actually be recognized in linear time. Beyond this result, we consider that this type of characterization is very useful, leads to a rich structure of classes, and generates a lot of open questions worth investigating., Third version version. 38 pages
Published: 2018

41. Search and broadcast in stochastic environments, a biological perspective

Author: Boczkowski, Lucas, Centre National de la Recherche Scientifique (CNRS), 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), Université Paris 7, Amos Korman, Iordanis Kerenidis, and Boczkowski, Lucas
Subjects: Algorithmes biologiques - Dissémination d'informations - Recherche robuste - Complexité moyenne - Erreurs permanentes - Communication bruitée, [INFO]Computer Science [cs], Biological algorithms - Information dissemination - Fault tolerant search - Average case analysis - Permanent faults - Noisy communication, [INFO] Computer Science [cs]
Abstract: This thesis is built around two series of works, each motivated by experiments on ants. We derive and analyse new models, that use computer science concepts and methodology, despite their biological roots and motivation.The first model studied in this thesis takes its inspiration in collaborative transport of food in the P. Longicornis species. We find that some key aspects of the process are well described by a graph search problem with noisy advice. The advice corresponds to characteristic short scent marks laid in front of the load in order to facilitate its navigation. In this thesis, we provide detailed analysis of the model on trees, which are relevant graph structures from a computer science standpoint. In particular our model may be viewed as a noisy extension of binary search to trees. Tight results in expectation and high probability are derived with matching upper and lower bounds. Interestingly, there is a sharp phase transition phenomenon for the expected runtime, but not when the algorithms are only required to succeed with high probability.The second model we work with was initially designed to capture information broadcast amongst desert ants. The model uses a stochastic meeting pattern and noise in the interactions, in a way that matches experimental data. Within this theoretical model, we present in this document a strong lower bound on the number of interactions required before information can be spread reliably. Experimentally, we see that the time required for the recruitment process of even few ants increases sharply with the group size, in accordance with our result. A theoretical consequence of the lower bound is a separation between the uniform noisy PUSH and PULL models of interaction. We also study a close variant of broadcast, without noise this time but under more strict convergence requirements and show that in this case, the problem can be solved efficiently, even with very limited exchange of information on each interaction., Cette thèse s’articule autour de deux séries de travaux motivés par des expériences sur des fourmis. Bien qu’inspirés par la biologie, les modèles que nous développons utilisent une terminologie et une approche typique de l’informatique théorique. Le premier modèle s’inspire du transport collaboratif de nourriture au sein de l’espèce P. Longicornis. Certains aspects fondamentaux du processus peuvent être décrits par un problème de recherche sur un graphe augmenté d'un certain type d’indications bruitées à chaque noeud. Ces indications représentent de courtes traces de phéromones déposées devant l’objet transporté afin de faciliter la navigation. Dans cette thèse, nous donnons une analyse complète du problème lorsque le graphe sous-jacent est un arbre, une hypothèse pertinente dans un cadre informatique. En particulier, notre modèle peut être vu comme une généralisation de la recherche binaire aux arbres en présence de bruit. De manière surprenante, les comportements des algorithmes optimaux dans ce cadre diffèrent suivant le type de garantie que l’on étudie : convergence en moyenne ou avec grande probabilité.Le deuxième modèle présenté dans cette thèse décrit la diffusion d’informations au sein de fourmis du désert. Dans notre modèle, les échanges ont lieu uniformément au hasard, et sont sujets à du bruit. Nous prouvons une borne inférieure sur le nombre d’interactions requis en fonction de la taille du groupe. La borne, de même que les hypothèses du modèle, semblent compatible avec les données expérimentales. Une conséquence théorique de ce résultat est une séparation dans ce cadre des variantes PUSH et PULL pour le problème du broadcast avec bruit. Nous étudions aussi une version du problème avec des garanties de convergence plus fortes. Dans ce cas, le problème peut être résolu efficacement, même si les messages échangés au cours de chaque interaction sont très limités.
Published: 2018

42. Décomposition de graphes en plus courts chemins et en cycles de faible excentricité

Author: Planche, Léo, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Mathématiques Appliquées Paris 5 (MAP5 - UMR 8145), Université Paris Descartes - Paris 5 (UPD5)-Institut National des Sciences Mathématiques et de leurs Interactions (INSMI)-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), Université Sorbonne Paris Cité, and Étienne Birmelé
Subjects: Cycle isométrique, Shortest path, Plus court chemin, Graphe de reads, Laminaire, Domination, Distance labeling, Isometric cycle, Laminarity, Eccentricity, Graph theory, [MATH.MATH-GM]Mathematics [math]/General Mathematics [math.GM], Read graphs, Excentricité, Théorie des graphes, Label de distances
Abstract: In collaboration with reserchears in biology at Université Pierre et Marie Curie, we study graphs coming from biological data in order to improve our understanding of it. Those graphs come from DNA fragments, named reads. Each read is a vertex and two vertices are linked if the DNA sequences are similar enough. Such graphs have a particuliar structure that we name hub-laminar. A graph is said to be hub-laminar if it may be represented as a (small) set of shortest paths such that every vertex of the graph is close to one of those paths. We first study the case where the graph is composed of an unique shortest path of low eccentricity. This problem was first definied by Dragan 2017. We improve the proof of an approximation algorithm already existing and propose a new one, a 3-approximation running in linear time. Furthermore we show its link with the k-laminar problem defined by Habib 2016, consisting in finding a diameter of low eccentricity. We then define and study the problem of the isometric cycle of minimal eccentricity. We show that this problem is NP-complete and propose two approximation algorithms. We then properly define what is an hub-laminar decomposition and we show an approximation algorithm running in O(nm). We test this algorithm with randomly generated graphs and apply it to our biolgical data. Finaly we show that computing an isometric cycle of low eccentricity allows to embed a graph into a cycle with a low multiplicative distortion. Computing an hub-laminar decomposition allows a compact representation of distances with a low additive distortion.; En collaboration avec des chercheurs en biologie à Jussieu, nous étudions des graphes issus de données biologiques afin de d'en améliorer la compréhension. Ces graphes sont constitués à partir de fragments d'ADN, nommés reads. Chaque read correspond à un sommet, et deux sommets sont reliés si les deux séquences d'ADN correspondantes ont un taux de similarité suffisant. Ainsi se forme des graphes ayant une structure bien particulière que nous nommons hub-laminaire. Un graphe est dit hub-laminaire s'il peut être résumé en quelques plus courts chemins dont tous les sommets du graphe soient proche. Nous étudions en détail le cas où le graphe est composé d'un unique plus court chemin d'excentricité faible, ce problème a été initialement défini par Dragan 2017. Nous améliorons la preuve d'un algorithme d'approximation déjà existant et en proposons un nouveau, effectuant une 3-approximation en temps linéaire. De plus, nous analysons le lien avec le problème de k-laminarité défini par Habib 2016, ce dernier consistant en la recherche d'un diamètre de faible excentricité. Nous étudions ensuite le problème du cycle isométrique de plus faible excentricité. Nous montrons que ce problème est NP-complet et proposons deux algorithmes d'approximations. Nous définissons ensuite précisément la structure "hub-laminaire" et présentons un algorithme d'approximation en temps O(nm). Nous confrontons cet algorithme à des graphes générés par une procédure aléatoire et l'appliquons à nos données biologiques. Pour finir nous montrons que le calcul du cycle isométrique d'excentricité minimale permet le plongement d'un graphe dans un cercle avec une distorsion multiplicative faible. Le calcul d'une décomposition hub-laminaire permet quant à lui une représentation compacte des distances avec une distorsion additive bornée.
Published: 2018

43. Representation of lattices via set-colored posets

Author: Michel Habib, Lhouari Nourine, 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), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020]), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), and Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne (UCA)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Antimatroid, Set-colored poset, Applied Mathematics, High Energy Physics::Lattice, 010102 general mathematics, Lattice, Representation theory, Upper locally distributive lattice, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 16. Peace & justice, 01 natural sciences, Combinatorics, Closure system, Colored, Distributive property, 010201 computation theory & mathematics, Lattice (order), Discrete Mathematics and Combinatorics, 0101 mathematics, Mathematics
Abstract: International audience; This paper proposes a representation theory for any finite lattice via set-colored posets, in the spirit of Birkhoff for distributive lattices. The notion of colored posets was introduced in Nourine (2000) [34] and the generalization to set-colored posets was given in Nourine (2000) [35]. In this paper, we give a characterization of set-colored posets for general lattices, and show that set-colored posets capture the order induced by join-irreducible elements of a lattice as Birkhoff’s representation does for distributive lattices. We also give a classification for some lattices according to the coloring property of their set-colored representation including upper locally distributive, upper locally distributive, meet-extremal and semidistributive lattices.
Published: 2018

44. Parameterized Complexity of Independent Set in H-Free Graphs

Author: Édouard Bonnet, Pierre Charbit, Rémi Watrigant, Nicolas Bousquet, Stéphan Thomassé, Centre National de la Recherche Scientifique (CNRS), Université de Lyon, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon), Modèles de calcul, Complexité, Combinatoire (MC2), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Optimisation Combinatoire (G-SCOP_OC ), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), 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), 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.), Université Claude Bernard Lyon 1 (UCBL), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), ANR-17-CE40-0015,DISTANCIA,Théorie métrique des graphes(2017), Optimisation Combinatoire (G-SCOP_OC), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), École normale supérieure de Lyon (ENS de Lyon), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), OC (G-SCOP_OC), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS), and ANR-11-IDEX-0007-02/10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2011)
Subjects: FOS: Computer and information sciences, Polynomial, General Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Induced subgraph, Parameterized complexity, 0102 computer and information sciences, 02 engineering and technology, Computational Complexity (cs.CC), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Combinatorics, Computer Science - Data Structures and Algorithms, 0202 electrical engineering, electronic engineering, information engineering, Data Structures and Algorithms (cs.DS), [MATH]Mathematics [math], Finite set, ComputingMilieux_MISCELLANEOUS, Mathematics, Disjoint union, 000 Computer science, knowledge, general works, H-Free Graphs, Parameterized Algorithms, Applied Mathematics, Independent Set, Parametrized complexity, 16. Peace & justice, Computer Science Applications, Computer Science - Computational Complexity, 010201 computation theory & mathematics, Independent set, Theory of computation, Computer Science, Iterative compression, 020201 artificial intelligence & image processing, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: In this paper, we investigate the complexity of Maximum Independent Set (MIS) in the class of $H$-free graphs, that is, graphs excluding a fixed graph as an induced subgraph. Given that the problem remains $NP$-hard for most graphs $H$, we study its fixed-parameter tractability and make progress towards a dichotomy between $FPT$ and $W[1]$-hard cases. We first show that MIS remains $W[1]$-hard in graphs forbidding simultaneously $K_{1, 4}$, any finite set of cycles of length at least $4$, and any finite set of trees with at least two branching vertices. In particular, this answers an open question of Dabrowski et al. concerning $C_4$-free graphs. Then we extend the polynomial algorithm of Alekseev when $H$ is a disjoint union of edges to an $FPT$ algorithm when $H$ is a disjoint union of cliques. We also provide a framework for solving several other cases, which is a generalization of the concept of \emph{iterative expansion} accompanied by the extraction of a particular structure using Ramsey's theorem. Iterative expansion is a maximization version of the so-called \emph{iterative compression}. We believe that our framework can be of independent interest for solving other similar graph problems. Finally, we present positive and negative results on the existence of polynomial (Turing) kernels for several graphs $H$., An extended abstract appeared in the proceedings of IPEC 2018
Published: 2018

45. EPTAS for Max Clique on Disks and Unit Balls

Author: Marthe Bonamy, Edouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stephan Thomasse, 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), Centre National de la Recherche Scientifique (CNRS), Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Optimisation Combinatoire (G-SCOP_OC ), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Networks, Graphs and Algorithms (GANG), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), 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), Université Paris Diderot - Paris 7 (UPD7)-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.), ANR-17-CE40-0015,DISTANCIA,Théorie métrique des graphes(2017), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), 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-Université Bordeaux Segalen - Bordeaux 2, OC (G-SCOP_OC), and Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Computational Geometry (cs.CG), FOS: Computer and information sciences, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 68Q25, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, 010201 computation theory & mathematics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], 0202 electrical engineering, electronic engineering, information engineering, Computer Science - Computational Geometry, F.2.2
Abstract: We propose a polynomial-time algorithm which takes as input a finite set of points of $\mathbb R^3$ and compute, up to arbitrary precision, a maximum subset with diameter at most $1$. More precisely, we give the first randomized EPTAS and deterministic PTAS for Maximum Clique in unit ball graphs. Our approximation algorithm also works on disk graphs with arbitrary radii. Almost three decades ago, an elegant polynomial-time algorithm was found for Maximum Clique on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematics '90]. Since then, it has been an intriguing open question whether or not tractability can be extended to general disk graphs. Recently, it was shown that the disjoint union of two odd cycles is never the complement of a disk graph [Bonnet, Giannopoulos, Kim, Rz\k{a}\.{z}ewski, Sikora; SoCG '18]. This enabled the authors to derive a QPTAS and a subexponential algorithm for Max Clique on disk graphs. In this paper, we improve the approximability to a randomized EPTAS (and a deterministic PTAS). More precisely, we obtain a randomized EPTAS for computing the independence number on graphs having no disjoint union of two odd cycles as an induced subgraph, bounded VC-dimension, and large independence number. We then address the question of computing Max Clique for disks in higher dimensions. We show that intersection graphs of unit balls, like disk graphs, do not admit the complement of two odd cycles as an induced subgraph. This, in combination with the first result, straightforwardly yields a randomized EPTAS for Max Clique on unit ball graphs. In stark contrast, we show that on ball and unit 4-dimensional disk graphs, Max Clique is NP-hard and does not admit an approximation scheme even in subexponential-time, unless the Exponential Time Hypothesis fails., Comment: 19 pages, 3 figures
Published: 2018

46. Reinforcement Learning Enables Resource Partitioning in Foraging Bats

Author: Michal Handel, Simon Collet, Aya Goldshtein, Stefan Greif, Rodrigo A. Medellín, Amos Korman, Yossi Yovel, Talia Shaler, Yuval Emek, Afrine Bonstein, Ofri Eitan, Tel Aviv University (TAU), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Universidad Nacional Autónoma de México = National Autonomous University of Mexico (UNAM), Technion - Israel Institute of Technology [Haifa], Networks, Graphs and Algorithms (GANG), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Tel Aviv University [Tel Aviv], Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Universidad Nacional Autónoma de México (UNAM), and Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)
Subjects: 0301 basic medicine, reinforcement learning, Resource (biology), Movement, Foraging, trapline, nectar feeding bats, reinforcement learning, resource partitioning, trapline, behavioral ecology, movement ecology, territories, Biology, territories, General Biochemistry, Genetics and Molecular Biology, Wearable Electronic Devices, 03 medical and health sciences, 0302 clinical medicine, ddc:570, Report, Chiroptera, Behavioral ecology, Animals, Lactation, Reinforcement learning, Nectar, Full movement, Leptonycteris, resource partitioning, Behavior, Animal, Ecology, Aerial imaging, Feeding Behavior, behavioral ecology, biology.organism_classification, nectar feeding bats, 030104 developmental biology, Flight, Animal, movement ecology, Geographic Information Systems, Female, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], General Agricultural and Biological Sciences, 030217 neurology & neurosurgery
Abstract: Summary Every evening, from late spring to mid-summer, tens of thousands of hungry lactating female lesser long-nosed bats (Leptonycteris yerbabuenae) emerge from their roost and navigate over the Sonoran Desert, seeking for nectar and pollen [1, 2]. The bats roost in a huge maternal colony that is far from the foraging grounds but allows their pups to thermoregulate [3] while the mothers are foraging. Thus, the mothers have to fly tens of kilometers to the foraging sites—fields with thousands of Saguaro cacti [4, 5]. Once at the field, they must compete with many other bats over the same flowering cacti. Several solutions have been suggested for this classical foraging task of exploiting a resource composed of many renewable food sources whose locations are fixed. Some animals randomly visit the food sources [6], and some actively defend a restricted foraging territory [7, 8, 9, 10, 11] or use simple forms of learning, such as “win-stay lose-switch” strategy [12]. Many species have been suggested to follow a trapline, that is, to revisit the food sources in a repeating ordered manner [13, 14, 15, 16, 17, 18, 19, 20, 21, 22]. We thus hypothesized that lesser long-nosed bats would visit cacti in a sequenced manner. Using miniature GPS devices, aerial imaging, and video recordings, we tracked the full movement of the bats and all of their visits to their natural food sources. Based on real data and evolutionary simulations, we argue that the bats use a reinforcement learning strategy that requires minimal memory to create small, non-overlapping cacti-cores and exploit nectar efficiently, without social communication., Highlights • GPS and aerial imaging allowed monitoring both the foragers and their resource • Goldshtein et al. describe the longest nightly commute for a small animal (∼200 km) • Bats divide the cactus fields into small, non-overlapping foraging cores • A simple reinforcement-learning model can explain and reproduce the bats’ behavior, Goldshtein et al. monitor bats’ foraging behavior and their food resource using miniature GPS devices and aerial imaging. Bats divide the cactus fields into small, non-overlapping cores without aggressive behavior. A simple foraging model that is reminiscent of reinforcement learning and requires minimal memory can reproduce the bats’ behavior.
Published: 2020

47. On the complexity of the shortest-path broadcast problem

Author: Hovhannes A. Harutyunyan, Pierluigi Crescenzi, Geppino Pucci, Andrea Pietracaprina, Pierre Fraigniaud, Chiara Pierucci, Magnús M. Halldórsson, Université de Florence, Università degli Studi di Firenze = University of Florence [Firenze] (UNIFI), Networks, Graphs and Algorithms (GANG), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), 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), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), School of Computer Science [Reykjavik], Reykjavík University, Concordia University [Montreal], Universita degli Studi di Padova, ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), Università degli Studi di Firenze = University of Florence (UniFI), Università degli Studi di Padova = University of Padua (Unipd), Università degli Studi di Firenze [Firenze], and ANR-11-BS02-014,DISPLEXITY,Calculabilité et complexité en distribué(2011)
Subjects: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Shortest paths, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Combinatorics, Simple (abstract algebra), TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, Layered graphs, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Time complexity, Mathematics, Discrete mathematics, Spanning tree, Applied Mathematics, Multiplicative function, 020206 networking & telecommunications, Directed graph, Binary logarithm, Broadcast time, Communication networks, 010201 computation theory & mathematics, Shortest path problem, Node (circuits), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; We study the shortest-path broadcast problem in graphs and digraphs, where a message has to be transmitted from a source node s to all the nodes along shortest paths, in the classical telephone model. For both graphs and digraphs, we show that the problem is equivalent to the broadcast problem in layered directed graphs. We then prove that this latter problem is NP-hard, and therefore that the shortest-path broadcast problem is NP-hard in graphs as well as in digraphs. Nevertheless, we prove that a simple polynomial-time algorithm, called MDST-broadcast, based on min-degree spanning trees, approximates the optimal broadcast time within a multiplicative factor 3/2 in 3-layer digraphs, and O(log n/loglog n) in arbitrary multi-layer digraphs. As a consequence, one can approximate the optimal shortest-path broadcast time in polynomial time within a multiplicative factor 3/2 whenever the source has eccentricity at most 2, and within a multiplicative factor O(log n/\log\log n) in the general case, for both graphs and digraphs. The analysis of MDST-broadcast is tight, as we prove that this algorithm cannot approximate the optimal broadcast time within a factor smaller than Omega(log n/log\log n).
Published: 2016

48. Coûts de Synchronization dans les Programmes Parallèles et les Structures de Donnèes Simultanées

Author: Aksenov, Vitalii, ITMO University [Russia], Langages de programmation, types, compilation et preuves (GALLIUM), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Networks, Graphs and Algorithms (GANG), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), 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, Télécom ParisTech, ITMO University, Paris Diderot University, Petr Kuznetsov, Anatoly Shalyto, Carole Delporte, and Aksenov, Vitalii
Subjects: Algorithmes, Concurrent data structures, Structures de données simultanées, Synchronisation, Performance, Parallel programs, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Granularity control, Programmes parallèles, Synchronization, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Contrôle de la granularité, Algorithms
Abstract: To use the computational power of modern computing machines, we have to deal with concurrent programs. Writing efficient concurrent programs is notoriously difficult, primarily due to the need of harnessing synchronization costs. In this thesis, we focus on synchronization costs in parallel programs and concurrent data structures.First, we present a novel granularity control technique for parallel programs designed for the dynamic multithreading environment. Then in the context of concurrent data structures, we consider the notion of concurrency-optimality and propose the first implementation of a concurrency-optimal binary search tree that, intuitively, accepts a concurrent schedule if and only if the schedule is correct. Also, we propose parallel combining, a technique that enables efficient implementations of concurrent data structures from their parallel batched counterparts. We validate the proposed techniques via experimental evaluations showing superior or comparable performance with respect to state-of-the-art algorithms.From a more formal perspective, we consider the phenomenon of helping in concurrent data structures. Intuitively, helping is observed when the order of some operation in a linearization is fixed by a step of another process. We show that no wait-free linearizable implementation of stack using read, write, compare&swap and fetch&add primitives can be help-free, correcting a mistake in an earlier proof by Censor-Hillel et al. Finally, we propose a simple way to analytically predict the throughput of data structures based on coarse-grained locking., Pour utiliser la puissance de calcul des ordinateurs modernes, nous devons écrire des programmes concurrents. L’écriture de programme concurrent efficace est notoirement difficile, principalement en raison de la nécessité de gérer les coûts de synchronization. Dans cette thèse, nous nous concentrons sur les coûts de synchronisation dans les programmes parallèles et les structures de données concurrentes.D’abord, nous présentons une nouvelle technique de contrôle de la granularité pour les programmes parallèles conçus pour un environnement de multi-threading dynamique. Ensuite, dans le contexte des structures de données concurrentes, nous considérons la notion d’optimalité de concurrence (concurrency-optimality) et proposons la première implémentation concurrence-optimal d’un arbre binaire de recherche qui, intuitivement, accepte un ordonnancement concurrent si et seulement si l’ordonnancement est correct. Nous proposons aussi la combinaison parallèle (parallel combining), une technique qui permet l’implémentation efficace des structures de données concurrences à partir de leur version parallèle par lots. Nous validons les techniques proposées par une évaluation expérimentale, qui montre des performances supérieures ou comparables à celles des algorithmes de l’état de l’art.Dans une perspective plus formelle, nous considérons le phénomène d’assistance (helping) dans des structures de données concurrentes. On observe un phénomène d’assistance quand l’ordre d’une opération d’un processus dans une trace linéarisée est fixée par une étape d’un autre processus. Nous montrons qu’aucune implémentation sans attente (wait-free) linéarisable d’une pile utilisant les primitives read, write, compare&swap et fetch&add ne peut être “sans assistance” (help-free), corrigeant une erreur dans une preuve antérieure de Censor-Hillel et al. Finalement, nous proposons une façon simple de prédire analytiquement le débit (throughput) des structures de données basées sur des verrous à gros grains.
Published: 2018

49. Efficient Loop Detection in Forwarding Networks and Representing Atoms in a Field of Sets

Author: Boufkhad, Yacine, Linguaglossa, Leonardo, Mathieu, Fabien, Perino, Diego, Viennot, Laurent, Networks, Graphs and Algorithms (GANG), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), 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), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratory of Information, Network and Communication Sciences (LINCS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT)-Sorbonne Université (SU), Nokia Bell Labs [Nozay], and Telefonica Group
Subjects: Networking and Internet Architecture (cs.NI), FOS: Computer and information sciences, Computer Science - Networking and Internet Architecture, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Software-defined networking, Field of sets, Forwarding tables, Loop
Abstract: The problem of detecting loops in a forwarding network is known to be NP-complete when general rules such as wildcard expressions are used. Yet, network analyzer tools such as Netplumber (Kazemian et al., NSDI'13) or Veriflow (Khurshid et al., NSDI'13) efficiently solve this problem in networks with thousands of forwarding rules. In this paper, we complement such experimental validation of practical heuristics with the first provably efficient algorithm in the context of general rules. Our main tool is a canonical representation of the atoms (i.e. the minimal non-empty sets) of the field of sets generated by a collection of sets. This tool is particularly suited when the intersection of two sets can be efficiently computed and represented. In the case of forwarding networks, each forwarding rule is associated with the set of packet headers it matches. The atoms then correspond to classes of headers with same behavior in the network. We propose an algorithm for atom computation and provide the first polynomial time algorithm for loop detection in terms of number of classes (which can be exponential in general). This contrasts with previous methods that can be exponential, even in simple cases with linear number of classes. Second, we introduce a notion of network dimension captured by the overlapping degree of forwarding rules. The values of this measure appear to be very low in practice and constant overlapping degree ensures polynomial number of header classes. Forwarding loop detection is thus polynomial in forwarding networks with constant overlapping degree.
Published: 2018

50. Implementing Snapshot Objects on Top of Crash-Prone Asynchronous Message-Passing Systems

Author: Hugues Fauconnier, Michel Raynal, Sergio Rajsbaum, Carole Delporte-Gallet, 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), Instituto de Matematicas [México], Universidad Nacional Autónoma de México = National Autonomous University of Mexico (UNAM), the World Is Distributed Exploring the tension between scale and coordination (WIDE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Universidad Nacional Autónoma de México (UNAM), 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.), As Scalable As Possible: foundations of large scale dynamic distributed systems (ASAP), SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), ASAP INRIA de Rennes, Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Inria Rennes – Bretagne Atlantique, Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Université de Rennes (UNIV-RENNES)-CentraleSupélec-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec, Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), and Raynal, Michel
Subjects: Linearizability, Computer science, Distributed computing, message passing, [SCCO.COMP]Cognitive science/Computer science, Crash, 0102 computer and information sciences, 02 engineering and technology, Parallel computing, [INFO] Computer Science [cs], Pro-cess crash failure, 01 natural sciences, shared memory, 020204 information systems, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], 0202 electrical engineering, electronic engineering, information engineering, Concurrent computing, [INFO]Computer Science [cs], Snapshot object, Distributed shared memory, Message passing, snapshot, 020206 networking & telecommunications, Atomic read/write register, Asynchronous message-passing system, Computational Theory and Mathematics, Shared memory, 010201 computation theory & mathematics, Hardware and Architecture, Asynchronous communication, Signal Processing, Snapshot (computer storage), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: In asynchronous crash-prone read/write shared-memory systems there is the notion of a snapshot object, which simulates the behavior of an array of single-writer/multi-reader (SWMR) shared registers that can be read atomically. Processes in the system can access the object invoking (any number of times) two operations, denoted $\mathsf {write}()$ and $\mathsf {snapshot}()$ . A process invokes $\mathsf {write}()$ to update the value of its register in the array. When it invokes $\mathsf {snapshot}()$ , the process obtains the values of all registers, as if it read them simultaneously. It is known that a snapshot object can be implemented on top of SWMR registers, tolerating any number of process failures. Snapshot objects provide a level of abstraction higher than individual SWMR registers, and they simplify the design of applications. Building a snapshot object on an asynchronous crash-prone message-passing system has similar benefits. The object can be implemented by using the known simulations of a SWMR shared memory on top of an asynchronous message-passing system (if less than half the processes can crash), and then build a snapshot object on top of the simulated SWMR memory. This paper presents an algorithm that implements a snapshot object directly on top of the message-passing system, without building an intermediate layer of a SWMR shared memory. To the authors knowledge, the proposed algorithm is the first providing such a direct construction. The algorithm is more efficient than the indirect solution, yet relatively simple.
Published: 2018

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

Select search scope, currently: Articles Catalog books, media & more in Jio Institute collections Articles journal articles & other e-resources

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Journal

Database

Publisher

290 results on '"Networks, Graphs and Algorithms (GANG)"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources