Author: "Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE)" - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE)"' showing total 492 results

Start Over Author "Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE)"

492 results on '"Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE)"'

1. Report on GRASTA 2017, 6th Workshop on GRAph Searching, Theory and Applications, Anogia, Crete, Greece, April 10 – April 13, 2017

Author: Angelopoulos, Spyros, Fraigniaud, Pierre, Fomin, Fedor V., Nisse, Nicolas, Thilikos, Dimitrios M., Recherche Opérationnelle (RO), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-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), Department of Informatics, University of Bergen (UIB), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), 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), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Department of Mathematics [Athens], National and Kapodistrian University of Athens = University of Athens (NKUA | UoA), LIP6, CNRS, Universit ́e Pierre et Marie Curie Paris, France, Department of Informatics, University of Bergen, Bergen, Norway, CNRS and Université Paris Diderot, France, Inria & Université Nice Sophia Antipolis, CNRS, I3S, Sophia Antipolis, France, AlGCo project team, CNRS, LIRMM, Montpellier, France, Department of Informatics [Bergen] (UiB), University of Bergen (UiB), 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), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), 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), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), National and Kapodistrian University of Athens (NKUA), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract: Graph searching involves a team of mobile agents (called searchers or pursuers or cops) that aims at capturing a set of escaping agents (called evaders or fugitives or robbers) that hide in a network modeled by a graph. There are many variants of graph searching studied in the literature, often referred to as a pursuit-evasion game or cops and robbers game. These variants are either application driven, i.e. motivated by problems in practice, or are inspired by foundational issues at the intersection of Computer Science, Discrete Mathematics, and Artificial Inteligence. As a result, many researchers from different areas of Mathematics, Computer Science and Operations Research are interested in problems related to graph searching.GRASTA 2017 is the main forum on graph searching and was held at the Anogia Academic Village, Anogia, Crete, Greece.It gathered 39 researchers from diverse areas of Theoretical Computer Science and Discrete Mathematics related to Graph Searching Games and their Applications both from the applied and the theoretical point of view. The scientific program of the workshop consisted of 18 regular talks, and an open problem session.
Published: 2017

2. Finding an induced subdivision of a digraph

Author: Frédéric Havet, Nicolas Trotignon, Jørgen Bang-Jensen, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Department of Mathematics and Computer Science [Odense] (IMADA), University of Southern Denmark (SDU), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Financial support from the Danish National Science research council (FNU) (under grant no. 09-066741)., Electronic Notes on Discrete Mathematics, ANR-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009), 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 INRIA
Subjects: FOS: Computer and information sciences, Polynomial, Discrete Mathematics (cs.DM), General Computer Science, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Mathematical proof, 01 natural sciences, Theoretical Computer Science, Combinatorics, 3-SAT, Computer Science::Discrete Mathematics, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, 05C85, Mathematics, Subdivision, Discrete mathematics, Mathematics::Combinatorics, business.industry, Applied Mathematics, 020206 networking & telecommunications, Digraph, Graph, NP-completeness, induced paths and cycles, 010201 computation theory & mathematics, Combinatorics (math.CO), linkings, business, Computer Science(all), Computer Science - Discrete Mathematics, digraphs
Abstract: International audience; We consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) G, does it contain an induced subdivision of a prescribed digraph D? The complexity of this problem depends on D and on whether G must be an oriented graph or is allowed to contain 2-cycles. We give a number of examples of polynomial instances as well as several NP-completeness proofs.
Published: 2012
Full Text: View/download PDF

3. GMPLS label space minimization through hypergraph layouts

Author: Ignasi Sau, Joanna Moulierac, David Coudert, Fernando Solano Donado, Stéphane Pérennes, Jean-Claude Bermond, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Institute of Telecommunications, Warsaw University of Technology [Warsaw], 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 Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Hypergraph, Theoretical computer science, General Computer Science, optical networks, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], hypergraph layout, 0202 electrical engineering, electronic engineering, information engineering, approximation algorithms, Mathematics, dynamic programming, Packet forwarding, Approximation algorithm, 020206 networking & telecommunications, Dynamic programming, GMPLS, 010201 computation theory & mathematics, Label switching, Path (graph theory), Graph (abstract data type), Routing (electronic design automation), label stacking, Computer Science(all)
Abstract: International audience; All-Optical Label Switching (AOLS) is a new technology that performs packet forwarding without any optical-electrical-optical conversions. In this paper, we study the problem of routing a set of requests in AOLS networks using GMPLS technology, with the aim of minimizing the number of labels required to ensure the forwarding. We first formalize the problem by associating to each routing strategy a logical hypergraph, called a hypergraph layout, whose hyperarcs are dipaths of the physical graph, called tunnels in GMPLS terminology. We define a cost function for the hypergraph layout, depending on its total length plus its total hop count. Minimizing the cost of the design of an AOLS network can then be expressed as finding a minimum cost hypergraph layout. We prove hardness results for the problem, namely for general directed networks we prove that it is NP-hard to find a C log n-approximation, where C is a positive constant and n is the number of nodes of the network. For symmetric directed networks, we prove that the problem is APX-hard. These hardness results hold even if the traffic instance is a partial broadcast. On the other hand, we provide approximation algorithms, in particular an O(log n)-approximation for symmetric directed networks. Finally, we focus on the case where the physical network is a directed path, providing a polynomial-time dynamic programming algorithm for a fixed number k of sources running in O(n^{k+2}) time.
Published: 2012
Full Text: View/download PDF

4. Engineering a New Algorithm for Distributed Shortest Paths on Dynamic Networks

Author: Gianlorenzo D'Angelo, Serafino Cicerone, Daniele Frigioni, Gabriele Di Stefano, Vinicio Maurizio, University of L'Aquila [Italy] (UNIVAQ), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Dynamic algorithm, Dynamic network analysis, General Computer Science, Computer science, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Enhanced Interior Gateway Routing Protocol, 0102 computer and information sciences, 02 engineering and technology, Floyd–Warshall algorithm, Network topology, 01 natural sciences, Routing Information Protocol, 0202 electrical engineering, electronic engineering, information engineering, Applied Mathematics, Node (networking), 020206 networking & telecommunications, Concurrent update, Distributed networks, Computer Science Applications, 010201 computation theory & mathematics, K shortest path routing, Enhanced Data Rates for GSM Evolution, Algorithm, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; We study the problem of dynamically updatingall-pairs shortest paths in a distributed network while edge update operations occur to the network. We consider the practical case of a dynamic network in which an edge update can occur while one or more other edge updates are under processing. A node of the network might be affected by a subset of these changes, thus being involved in the concurrent executions related to such changes. In this paper, we provide a new algorithm for this problem, and experimentally compare its performance with respect to those of the most popular solutions in the literature: the classical distributed Bellman-Ford method, which is still used in real network and implemented in the RIP protocol, and DUAL, the Diffuse Update ALgorithm, which is part of CISCO's widely used EIGRP protocol. As input to the algorithms, we used both real-world and artificial instances of the problem. The experiments performed show that the space occupancy per node required by the new algorithm is smaller than that required by both Bellman-Ford and DUAL. In terms of messages, the new algorithm outperforms both Bellman-Ford and DUAL on the real-world topologies, while on artificial instances, the new algorithm sends a number of messages that is more than that of DUAL and much smaller than that of Bellman-Ford.
Published: 2012
Full Text: View/download PDF

5. Framework for optimizing the capacity of wireless mesh networks

Author: Stéphane Pérennes, Hervé Rivano, Christelle Caillouet, Laboratoire d'Informatique de Grenoble (LIG), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Smart Wireless Networking (SWING), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CITI Centre of Innovation in Telecommunications and Integration of services (CITI), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Dynamic Source Routing, business.product_category, Computer Networks and Communications, Computer science, Distributed computing, Wireless mesh networks, Wireless Routing Protocol, Geographic routing, 02 engineering and technology, Shared mesh, Scheduling (computing), [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Default gateway, Computer Science::Networking and Internet Architecture, 0202 electrical engineering, electronic engineering, information engineering, Internet access, scheduling, column and cut generation, Static routing, Wireless mesh network, business.industry, capacity, Quality of service, ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS, linear programming, 020206 networking & telecommunications, Order One Network Protocol, routing, 020201 artificial intelligence & image processing, Hazy Sighted Link State Routing Protocol, business, Computer network
Abstract: International audience; In this paper, we address the problem of computing the transport capacity of Wireless Mesh Networks (WMNs) dedicated to Internet access. Routing and transmission scheduling have a major impact on the capacity provided to the clients. A cross-layer optimization of these problems allows the routing to take into account contentions due to radio interference. We present a generic Mixed Integer Linear Programing description of the congurations of a given WMN, addressing gateway placement, routing, and scheduling optimizations. We then develop new optimization models that can take into account a large variety of radio interference models, and QoS requirements on the routing. We also provide efficient resolution methods that deal with realistic size instances. It allows to work around the combinatoric of simultaneously achievable transmissions and point out a critical region in the network bounding the network achievable capacity. Based upon strong duality arguments, it is then possible to restrict the computation to a bounded area. It allows for computing solutions very efficiently on large networks.
Published: 2011
Full Text: View/download PDF

6. Applying Cellular Automata and DEVS Methodologies to Digital Games: A Survey

Author: Olivier Dalle, Gabriel Wainer, Bernard P. Zeigler, Qi Liu, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Advanced Real-Time Simulation Laboratory (ARS), Carleton University, Department of Electrical and Computer Engineering [Tucson] (ECE), University of Arizona, EA DISSIMINET (Associated Team), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: 021103 operations research, DEVS, Theoretical computer science, Computer science, 05 social sciences, 0211 other engineering and technologies, 050301 education, General Social Sciences, 02 engineering and technology, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, Cellular automaton, Computer Science Applications, Modeling and simulation, symbols.namesake, ACM: I.: Computing Methodologies/I.6: SIMULATION AND MODELING, Systems theory, symbols, Automata theory, Discrete event simulation, 0503 education, Social simulation, Von Neumann architecture
Abstract: International audience; Cellular automata were designed by John von Neumann in the 1940s, as a mathematical abstraction for modeling self-replicating algorithms. Since then, cellular automata have been widely studied theoretically and evolved into multiple variants. In the 1970s, Bernard P. Zeigler proposed a formalism rooted on systems theory principles, named DEVS (discrete-event systems specifications), which paved the way for component-based modeling and simulation and related methodologies. The purpose of this article is to survey how cellular automata and its variant, called cell-DEVS, may be used to implement computer simulations that can be used as digital serious games. The authors illustrate that implementation through some of the practical applications of such cellular automata. They show various serious game applications using real case studies: first, a simple bouncing ball and pinball game, a particle collision model, another on gossip propagation, and an application on human behavior at a metro station. Then, they show an application to social simulation using a voters game, a theoretical application (a model called Daisy World, which is derived from Gaia theory), and applications to physical phenomena such as a sandpile formation model or, finally, a three-dimensional model of a "virtual clay" that changes its shape when it is subject to pressure effects.
Published: 2010
Full Text: View/download PDF

7. Power-efficient radio configuration in fixed broadband wireless networks

Author: Hervé Rivano, Napoleão Nepomuceno, David Coudert, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (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), Universidade Federal do Ceará = Federal University of Ceará (UFC), Smart Wireless Networking (SWING), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CITI Centre of Innovation in Telecommunications and Integration of services (CITI), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA), Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: Mathematical optimization, 021103 operations research, Computer Networks and Communications, Wireless network, Broadband networks, business.industry, Heuristic (computer science), Computer science, 0211 other engineering and technologies, ACM: C.: Computer Systems Organization/C.2: COMPUTER-COMMUNICATION NETWORKS/C.2.1: Network Architecture and Design, 020206 networking & telecommunications, 02 engineering and technology, Energy consumption, Multi-commodity flow problem, Piecewise linear function, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Total energy expenditure, Wireless broadband, 0202 electrical engineering, electronic engineering, information engineering, Piecewise, ACM: C.: Computer Systems Organization/C.2: COMPUTER-COMMUNICATION NETWORKS/C.2.1: Network Architecture and Design/C.2.1.10: Wireless communication, business
Abstract: International audience; In this work, we investigate on determining feasible radio configurations in fixed broadband wireless networks, focusing on power efficiency. Under this scenario, a power-efficient configuration can be characterized by a modulation constellation size and a transmission power level. Every link holds a set of power-efficient configurations, each of them associating a capacity with its energy cost. We introduce a joint optimization of data routing and radio configuration that minimizes the total energy consumption while handling all the traffic requirements simultaneously. An exact mathematical formulation of the problem is presented. It relies on a minimum cost multicommodity flow with step increasing cost functions, which is very hard to optimize. We then propose a piecewise linear convex function, obtained by linear interpolation of power-efficient points, that provides a good approximation of the energy consumption on the links, and present a relaxation of the previous formulation that exploits the convexity of the cost functions. This yields lower bounds on the total energy expenditure, and finally heuristic algorithms based on the fractional optimum are employed to produce feasible configuration solutions. Our models are validated through extensive experiments that are reported and discussed. The results testify the potentialities behind this novel approach.
Published: 2010
Full Text: View/download PDF

8. The cost of monotonicity in distributed graph searching

Author: Nicolas Nisse, David Soguet, David Ilcinkas, Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Additional supports from the project 'Fragile' of the ACI Sécurité Informatique, and from the project 'Grand Large' of INRIA., Eduardo Tovar, Philippas Tsigas, Hacène Fouchal, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Monotonicity, Mathematical optimization, Theoretical computer science, Computer Networks and Communications, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 050801 communication & media studies, 0102 computer and information sciences, 02 engineering and technology, Strength of a graph, Biconnected graph, 01 natural sciences, Theoretical Computer Science, law.invention, 0508 media and communications, Graph power, law, Line graph, 0202 electrical engineering, electronic engineering, information engineering, Graph property, Complement graph, Graph searching, Distance-hereditary graph, Mobile agent, Discrete mathematics, 020203 distributed computing, 05 social sciences, Voltage graph, Directed graph, Butterfly graph, Competitive ratio, Graph bandwidth, Computational Theory and Mathematics, 010201 computation theory & mathematics, Hardware and Architecture, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Null graph, Graph factorization, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; Blin {\it et al.} (2006) proposed a distributed protocol that enables the smallest number of searchers to clear any unknown asynchronous graph in a decentralized manner. {\it Unknown} means that the searchers are provided no {\it a priori} information about the graph. However, the strategy that is actually performed lacks of an important property, namely the monotonicity. That is, the clear part of the graph may decrease at some steps of the execution of the protocol. Actually, the protocol of Blin {\it et al.} is executed in exponential time. Nisse and Soguet (2007) proved that, in order to ensure the smallest number of searchers to clear any $n$-node graph in a monotone way, it is necessary and sufficient to provide $\Theta(n \log n)$ bits of information to the searchers by putting short labels on the nodes of the graph. This paper deals with the smallest number of searchers that are necessary and sufficient to monotoneously clear any graph in a decentralized manner, when the searchers have no a priori information about the graph. The distributed graph searching problem considers a team of searchers that is aiming at clearing any connected contaminated graph. The clearing of the graph is required to be {\it connected}, i.e., the clear part of the graph must remain permanently connected, and {\it monotone}, i.e., the clear part of the graph only grows. The {\it search number} $\mcs(G)$ of a graph $G$ is the smallest number of searchers necessary to clear $G$ in a monotone connected way in centralized settings. We prove that any distributed protocol aiming at clearing any unknown n-node graph in a monotone connected way, in decentralized settings, has {\it competitive ratio} $\Theta(\frac{n}{\log n})$. That is, we prove that, for any distributed protocol $\cal P$, there exists a constant $c$ such that for any sufficiently large $n$, there exists a $n$-node graph $G$ such that $\cal P$ requires at least $c\frac{n}{\log n}\, \mcs(G)$ searchers to clear $G$. Moreover, we propose a distributed protocol that allows $O(\frac{n}{\log n})\, \mcs(G)$ searchers to clear any unknown asynchronous $n$-node graph $G$ in a monotone connected way.
Published: 2009
Full Text: View/download PDF

9. Optimal gathering protocols on paths under interference constraints

Author: Ricardo C. Corrêa, Jean-Claude Bermond, Min-Li Yu, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (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), Departamento do Computacao [Fortaleza BR], Universidade Federal do Ceará = Federal University of Ceará (UFC), SFU Discrete Mathematics Group (SFU-DMG), Simon Fraser University (SFU.ca), IST FET AEOLUS, REGAL, E.A..ReseauxCom, CNPq, CAPES, Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: multi-hop radio networks, path, gathering algorithms, interference, Multi-hop radio network, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Upper and lower bounds, Theoretical Computer Science, [INFO.INFO-IU]Computer Science [cs]/Ubiquitous Computing, Radio networks, Reachability, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Communication source, Computer Science::Information Theory, Mathematics, Discrete mathematics, business.industry, ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS, Exposed node problem, 010201 computation theory & mathematics, Graph (abstract data type), 020201 artificial intelligence & image processing, business, Computer network
Abstract: A preliminary version has been presented at CIAC06; International audience; We study the problem of gathering information from the nodes of a multi-hop radio network into a predefined destination node under reachability and interference constraints. In such a network, a node is able to send messages to other nodes within reception distance, but doing so it might create interference with other communications. Thus, a message can only be properly received if the receiver is reachable from the sender and there is no interference from another message being transmitted simultaneously. The network is modeled as a graph, where the vertices represent the nodes of the network and the edges, the possible communications. The interference constraint is modeled by a fixed integer d?1, which implies that nodes within distance d in the graph from one sender cannot receive messages from another node. In this paper, we suppose that each node has one unit-length message to transmit and, furthermore, we suppose that it takes one unit of time (slot) to transmit a unit-length message and during such a slot we can have only calls which do not interfere (called compatible calls). A set of compatible calls is referred to as a round. We give protocols and lower bounds on the minimum number of rounds for the gathering problem when the network is a path and the destination node is either at one end or at the center of the path. These protocols are shown to be optimal for any d in the first case, and for d=1,2,3,4, in the second case.
Published: 2009
Full Text: View/download PDF

10. A general critical condition for the emergence of a giant component in random graphs with given degrees

Author: Nikolaos Fountoulakis, Bruce Reed, Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (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), Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: Random graph, Discrete mathematics, Degree (graph theory), Applied Mathematics, 0102 computer and information sciences, 01 natural sciences, Critical point (mathematics), Giant component, Least fixed point, Combinatorics, [INFO.INFO-MC]Computer Science [cs]/Mobile Computing, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], 010104 statistics & probability, 010201 computation theory & mathematics, Frequency partition of a graph, Random regular graph, Discrete Mathematics and Combinatorics, 0101 mathematics, Critical condition, Mathematics
Abstract: International audience; In this contribution, we investigate the giant component problem in random graphs with a given degree sequence. We generalize the critical condition of Molloy and Reed [Molloy, M., and B. Reed, A critical point for random graphs with given degree sequence, Random Structures Algorithms 6 (1995), 161-179], which determines the existence of a giant component in such a random graph, in order to include degree sequences with heavy tails. We show that the quantity which determines the existence of a giant component is the value of the smallest fixed point inside the interval [0, 1] of the generating function F(s)=∑i⩾1δisi−1, where δi is the asymptotic proportion of the total degree contained in vertices of degree i. Moreover, we show that this quantity also determines the existence of a core (i.e., the maximal subgraph of minimum degree at least 2) that has linear total degree.
Published: 2009
Full Text: View/download PDF

11. Fractionally Edge Colouring Graphs with Large Maximum Degree in Linear Time

Author: Conor Meagher, W. Sean Kennedy, Bruce Reed, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Discrete mathematics, Applied Mathematics, 010102 general mathematics, 0102 computer and information sciences, Edge (geometry), 01 natural sciences, Combinatorics, [INFO.INFO-MC]Computer Science [cs]/Mobile Computing, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], 010201 computation theory & mathematics, Simple (abstract algebra), Discrete Mathematics and Combinatorics, 0101 mathematics, Time complexity, Mathematics
Abstract: International audience; For any c>1, we describe a linear time algorithm for fractionally edge colouring simple graphs with maximum degree at least |V|/c.
Published: 2009
Full Text: View/download PDF

12. Minimal selectors and fault tolerant networks

Author: Amini, Omid, Giroire, Frédéric, Huc, Florian, Pérennes, Stéphane, Département de Mathématiques et Applications - ENS Paris (DMA), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (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 Universitaire d'Informatique, Université de Genève = University of Geneva (UNIGE), This work has been partially supported by European project IST FET AEOLUS, Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), 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), Université de Genève (UNIGE), and École normale supérieure - Paris (ENS Paris)
Subjects: [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], 021103 operations research, 010201 computation theory & mathematics, Computer Networks and Communications, Hardware and Architecture, 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Software, Information Systems
Abstract: International audience; In this paper we study a combinatorial optimization problem issued from on-board networks in satellites. In this kind of networks the entering signals (inputs) should be routed to amplifiers (outputs). The connections are made via expensive switches with four links available. The paths connecting inputs to outputs should be link-disjoint. More formally, we call it $\plk-$network an undirected graph with $p+\lambda$ inputs, $p+k$ outputs and internal vertices of degree four. A $\plk-$network is valid if it is tolerant to a restricted number of faults in the network, i.e. if for any choice of at most $k$ faulty inputs and $\lambda$ faulty outputs, there exist $p$ edge-disjoint paths from the remaining inputs to the remaining outputs. In the special case $\lambda=0$, a $\plk-$network is already known as a selector. Our optimization problem consists of determining $N\plk$, the minimum number of nodes in a valid $\plk-$network. For this, we present validity certificates and a gluing lemma from which derive lower bounds for $N\plk$. We also provide constructions, and hence upper bounds, based on expanders. The problem is very sensitive to the order of $\lambda$ and $k$. For instance, when $\lambda$ and $k$ are small compared to $p$, the question reduces to avoid certain forbidden local configurations. For larger values of $\lambda$ and $k$, the problem is to find graphs with a good expansion property for small sets. This leads us to introduce a new parameter called $\alpha$-robustness. We use $\alpha$-robustness to generalize our constructions to higher order values of $k$ and $\lambda$. In many cases, we provide asymptotically tight bounds for $N\plk$.
Published: 2009
Full Text: View/download PDF

13. Choosability of the square of planar subcubic graphs with large girth

Author: Frédéric Havet, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Discrete mathematics, 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Planar graph, Theoretical Computer Science, Choice number, Combinatorics, symbols.namesake, Planar, List colouring, 010201 computation theory & mathematics, Square of a graph, symbols, Discrete Mathematics and Combinatorics, 0101 mathematics, Bounded density, Mathematics
Abstract: International audience; We show that the choice number of the square of a subcubic graph with maximum average degree less than 18/7 is at most 6. As a corollary, we get that the choice number of the square of a subcubic planar graph with girth at least 9 is at most 6. We then show that the choice number of the square of a subcubic planar graph with girth at least 13 is at most 5.
Published: 2009
Full Text: View/download PDF

14. Improper colouring of (random) unit disk graphs

Author: Ross J. Kang, Tobias Müller, Jean-Sébastien Sereni, Department of Statistics [Oxford], University of Oxford [Oxford], Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Stefan Felsner, University of Oxford, 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), INRIA, and Eurandom
Subjects: General Computer Science, radio channel assignment, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], 0211 other engineering and technologies, Astrophysics::Cosmology and Extragalactic Astrophysics, 0102 computer and information sciences, 02 engineering and technology, CHROMATIC NUMBER, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, Indifference graph, Computer Science::Discrete Mathematics, unit disk graphs, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Random regular graph, Discrete Mathematics and Combinatorics, Channel assignment, Chromatic scale, Random geometric graph, Astrophysics::Galaxy Astrophysics, random unit disk graphs, Mathematics, Random graph, Discrete mathematics, UNIT DISK GRAPH, 021103 operations research, Unit disk graph, RANDOM GRAPH, CLIQUE NUMBER, Unit disk, Graph, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], 010201 computation theory & mathematics, improper colouring
Abstract: For any graph G, the k-improper chromatic [email protected]^k(G) is the smallest number of colours used in a colouring of G such that each colour class induces a subgraph of maximum degree k. We investigate @g^k for unit disk graphs and random unit disk graphs to generalise results of McDiarmid and Reed [Colouring proximity graphs in the plane, Discrete Math. 199(1-3) (1999) 123-137], McDiarmid [Random channel assignment in the plane, Random Structures Algorithms 22(2) (2003) 187-212], and McDiarmid and Muller [On the chromatic number of random geometric graphs, submitted for publication].
Published: 2008
Full Text: View/download PDF

15. Energy Efficient Content Distribution

Author: Frédéric Giroire, Yaning Liu, Remigiusz Modrzejewski, Joanna Moulierac, Júlio Araújo, Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), 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 (... - 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), JCP-Consult [Cesson-Sévigné], JCP-Consult, Région PACA. Conselho Nacional de Desenvolvimento Cientifico e Tecnologico, Brazil, under postdoctoral fellowship PDE 202049/2012-4., INRIA, ANR-18-CE23-0013,AGAPE,Un langage d'enchères pour des joueurs génériques d'enchères(2018), ANR-11-LABX-0031,UCN@SOPHIA,Réseau orienté utilisateur(2011), 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), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Google Inc., COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), 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), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Router, Future Internet, General Computer Science, Computer science, Energy Efficiency, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 050801 communication & media studies, Content delivery network, 02 engineering and technology, 7. Clean energy, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], 0508 media and communications, Content Delivery Network, In-network Caching, 0202 electrical engineering, electronic engineering, information engineering, Content Deliv-ery Network, Integer programming, Integer Linear Programming, Backbone network, business.industry, 05 social sciences, 020206 networking & telecommunications, Networking hardware, Network congestion, 020201 artificial intelligence & image processing, Multi-frequency network, Net- work Cache, Cache, Routing (electronic design automation), business, Computer network, Efficient energy use
Abstract: To optimize energy efficiency in network, operators try to switch off as many network devices as possible. Recently, there is a trend to introduce content caches as an inherent capacity of network equipment, with the objective of improving the efficiency of content distribution and reducing network congestion. In this work, we study the impact of using in-network caches and CDN cooperation on an energy-efficient routing. We formulate this problem as Energy Efficient Content Distribution. The objective is to find a feasible routing, so that the total energy con- sumption of the network is minimized subject to satisfying all the demands and link capacity. We exhibit the range of parameters (size of caches, popularity of content, demand intensity, etc.) for which caches are useful. Experiment results show that by placing a cache on each backbone router to store the most popular content, along with well choosing the best content provider server for each demand to a CDN, we can save a total up to 23% of power in the backbone, while 16% can be gained solely thanks to caches.; Pour optimiser l'efficacité énergétique dans un réseau, les opérateurs doivent éteindre un nombre maximum d'équipements réseau. Récemment, il a été propose de rajouter des caches à l'intérieur des nœuds réseaux dans l'objectif d'améliorer la distribution de contenus et de réduire la congestion des réseaux. Dans ce travail, nous étudions l'impact de l'utilisation de caches réseaux (in- network caches) et de leur coopération avec les Content Delivery Networks (CDN) sur l'énergie consommée par le routage. Nous modélisons ce problème, la Distribution de Données Efficace en Énergie. L'objectif est de trouver un routage réalisable qui minimise la consommation énergétique du réseau tout en satisfaisant les demandes de contenus. Nous exhibons les valeurs des paramètres (tailles des caches, popularités des données, ...) pour lesquelles ces caches sont utiles. Des expérimentations montrent qu'en plaçant un cache sur chaque routeur d'un réseau backbone pour stocker le contenu le plus populaire, ainsi qu'on choisissant le meilleur serveur pour chaque demande 'a un CDN, jusqu'à 23% de l'énergie du backbone peut être sauvée, dont 16% du gain est du aux seuls caches.
Published: 2016
Full Text: View/download PDF

16. On the Monotonicity of Process Number

Author: Ronan Pardo Soares, Nicolas Nisse, 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 (... - 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), Universidade Federal do Ceará = Federal University of Ceará (UFC), 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), Inria Chile, Universidad Diego Portales [Santiago] (UDP)-Universidad de la frontera [Chile]-Pontificia Universidad Católica de Chile (UC)-Institut National de Recherche en Informatique et en Automatique (Inria)-Pontificia Universidad Católica de Valparaíso (PUCV)-Universidad Adolfo Ibáñez [Santiago]-Universidad de Valparaiso [Chile]-Universidad Tecnica Federico Santa Maria [Valparaiso] (UTFSM)-Universidad de Concepción - University of Concepcion [Chile], Parallelism, Graphs and Optimization Research Group (ParGO), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), INRIA, Universidad Diego Portales [Santiago] (UDP)-Universidad de la frontera [Chile]-Universidad de Concepción [Chile]-Pontificia Universidad Católica de Chile (UC)-Institut National de Recherche en Informatique et en Automatique (Inria)-Pontificia Universidad Católica de Valparaíso (PUCV)-Universidad Adolfo Ibáñez [Santiago]-Universidad de Valparaiso [Chile]-Universidad Tecnica Federico Santa Maria [Valparaiso] (UTFSM), and Universidad de Valparaiso [Chile]-Universidad Tecnica Federico Santa Maria [Valparaiso] (UTFSM)-Universidad Adolfo Ibáñez [Santiago]-Pontificia Universidad Católica de Valparaíso (PUCV)-Institut National de Recherche en Informatique et en Automatique (Inria)-Pontificia Universidad Católica de Chile (UC)-Universidad de Concepción [Chile]-Universidad de la frontera [Chile]-Universidad Diego Portales [Santiago] (UDP)
Subjects: Strongly connected component, Computer Science::Computer Science and Game Theory, Monotonicity, Theoretical computer science, 0211 other engineering and technologies, 050801 communication & media studies, Monotonic function, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph Searching, 0508 media and communications, Pathwidth, Discrete Mathematics and Combinatorics, Game tree, Mathematics, Discrete mathematics, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Applied Mathematics, 05 social sciences, ComputingMilieux_PERSONALCOMPUTING, Control reconfiguration, 021107 urban & regional planning, Digraph, Directed graph, 16. Peace & justice, Modular decomposition, Monotone polygon, 010201 computation theory & mathematics, Process Number, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: Graph searching games involve a team of searchers that aims at capturing a fugitive in a graph. These games have been widely studied for their relationships with tree- and path-decomposition of graphs. In order to define decompositions for directed graphs, similar games have been proposed in directed graphs. In this paper, we consider such a game that has been defined and studied in the context of routing reconfiguration problems in WDM networks. Namely, in the processing game, the fugitive is invisible, arbitrary fast, it moves in the opposite direction of the arcs of a digraph, but only as long as it has access to a strongly connected component free of searchers. We prove that the processing game is monotone which leads to its equivalence with a new digraph decomposition.; Les jeux de capture impliquent une équipe d'agents qui doivent capturer un fugitif se déplaçant dans un graphe. Ces jeux ont été très étudiés pour leur interprétation en termes de décompositions de graphes (tree-decomposition, path-decomposition). Dans le but de définir de "bonnes" décompositions pour les graphes orientés, des jeux similaires ont été définis et étudiés dans les graphes orientés. Dans ce travail, nous considérons un jeu qui a été défini dans le contexte du routage dans les réseaux WDM. Dans ce jeu, le processing game, le fugitif est invisible, arbitrairement rapide et se déplace dans le sens opposé des arcs. De plus, le fugitif est capturé dès qu'il lui est impossible d'accéder à une composante fortement connexe sans agents. Nous prouvons que ce jeu est monotone. Cela permet de montrer l'équivalence du processing game et d'une nouvelle décomposition de graphes orientés.
Published: 2016

17. Optimalni algoritem za permutacijsko usmerjanje na heksagonalnih mrežah

Author: Ignasi Sau, Janez Zerovnik, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (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), Faculty of Mechanical Engineering [Maribor] (FME), University of Maribor, Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: shortest path, General Computer Science, Equal-cost multi-path routing, komunikacijsko omrežje, 02 engineering and technology, Source routing, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], heksagonalne mreže, permutacijsko usmerjanje, Theoretical Computer Science, porazdeljen algoritem, 0202 electrical engineering, electronic engineering, information engineering, Computer Science::Networking and Internet Architecture, Discrete Mathematics and Combinatorics, communication networks, Destination-Sequenced Distance Vector routing, oblivious algorithm, Triangular routing, Mathematics, distributed algorithm, Static routing, hexagonal networks, najkrajše poti, mathematics, lcsh:Mathematics, ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS, DSRFLOW, 020206 networking & telecommunications, pozabljiv algoritem, lcsh:QA1-939, permutation routing, udc:519.17, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Link-state routing protocol, matematika, 020201 artificial intelligence & image processing, Routing (electronic design automation), Algorithm
Abstract: Distributed Computing and Networking, In the permutation routing problem, each processor is the origin of at most one packet and the destination of no more than one packet. The goal is to minimize the number of time steps required to route all packets to their respective destinations, under the constraint that each link can be crossed simultaneously by no more than one packet. We study this problem in a hexagonal network, i.e. a finite subgraph of a triangular grid, which is a widely used network in practical applications. We present an optimal distributed permutation routing algorithm on full-duplex hexagonal networks, using the addressing scheme described by F.G. Nocetti, I. Stojmenovic and J. Zhang (IEEE TPDS 13(9): 962-971, 2002). Furthermore, we prove that this algorithm is oblivious and translation invariant.
Published: 2015
Full Text: View/download PDF

18. An Overview of MANETs Simulation

Author: Luc Hogie, Frédéric Guinand, Pascal Bouvry, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Université du Luxembourg (Uni.lu), Equipe Réseaux d'interactions et Intelligence Collective (RI2C - LITIS), Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Université Le Havre Normandie (ULH), Normandie Université (NU)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Université Le Havre Normandie (ULH), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: General Computer Science, Computer science, Distributed computing, MANETs, GloMoSim, 02 engineering and technology, Network interface, Mobile ad hoc networks, Theoretical Computer Science, Domain (software engineering), law.invention, Bluetooth, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], law, 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], Flexibility (engineering), Vehicular ad hoc network, business.industry, ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS, 020206 networking & telecommunications, Mobile ad hoc network, simulation, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, Key (cryptography), 020201 artificial intelligence & image processing, business, Computer Science(all), Computer network
Abstract: Open access: https://www.sciencedirect.com/science/article/pii/S1571066106001010; International audience; Mobile Ad hoc NETworks (MANETs) are dynamic networks populated by mobile stations. Stations in MANETs are usually laptops, PDAs or mobile phones. These devices feature Bluetooth and/or IEEE 802.11 (WiFi) network interfaces and communicate in a decentralized manner. Mobility is a key feature of MANETs. Because of their high cost and their lack of flexibility of such networks, experimentation is mostly achievable through simulation. Numerous tools exist for MANETs simulation, including ns-2 and GloMoSim which are the two most popular ones. This paper provides a State of the Art of MANETs simulators and associated simulation techniques. First it gives an overview of the domain. Then it provides a map of the main characteristics that MANETs simulation tools should feature and the current support of these. Finally, a description for each simulator is provided, including an explanation of what make them appealing solutions.
Published: 2006
Full Text: View/download PDF

19. Arc-chromatic number of digraphs in which every vertex has bounded outdegree or bounded indegree

Author: Bessy, Stéphane, Birmelé, Etienne, Havet, Frédéric, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Statistique et Génome (SG), Institut National de la Recherche Agronomique (INRA)-Université d'Évry-Val-d'Essonne (UEVE)-Centre National de la Recherche Scientifique (CNRS), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (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)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), 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), 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), and Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Mathematics::Combinatorics, Computer Science::Discrete Mathematics, 010201 computation theory & mathematics, 010102 general mathematics, Discrete Mathematics and Combinatorics, 0102 computer and information sciences, Geometry and Topology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 0101 mathematics, 01 natural sciences
Abstract: International audience; A {\it $k$-digraph} is a digraph in which every vertex has outdegree at most $k$. A {\it $(k\vee l)$-digraph} is a digraph in which a vertex has either outdegree at most $k$ or indegree at most $l$. Motivated by function theory, we study the maximum value $\Phi (k)$ (resp. $\Phi^{\vee}(k,l)$) of the arc-chromatic number over the $k$-digraphs (resp. $(k\vee l)$-digraphs). El-Sahili~\cite{ElS03} showed that $\Phi^{\vee}(k,k)\leq 2k+1$. After giving a simple proof of this result, we show some better bounds. We show $\max\{\log(2k+3), \theta(k+1)\}\leq \Phi(k)\leq \theta(2k)$ and $\max\{\log(2k+2l+4), \theta(k+1), \theta(l+1)\}\leq \Phi^{\vee}(k,l)\leq \theta(2k+2l)$ where $\theta$ is the function defined by $\ds \theta(k)=\min\{s : {s\choose \left\lceil \frac{s}{2}\right\rceil}\geq k\}$. We then study in more details properties of $\Phi$ and $\Phi^{\vee}$. Finally, we give the exact values of $\Phi(k)$ and $\Phi^{\vee}(k,l)$ for $l\leq k\leq 3$.
Published: 2006
Full Text: View/download PDF

20. Hierarchical Ring Network design

Author: Jean-Claude Bermond, Sébastien Choplin, Stéphane Pérennes, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (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), 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: Discrete mathematics, Ring (mathematics), Optimization problem, Node (networking), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Order (ring theory), Ring network, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Function (mathematics), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-SI]Computer Science [cs]/Social and Information Networks [cs.SI], Theoretical Computer Science, Combinatorics, Network planning and design, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Computational Theory and Mathematics, Combinatorial optimization, Mathematics
Abstract: A Hierarchical Ring Network is obtained from a ring network by appending at most one subsidiary ring to each node of the ring and, recursively, to each node of each subsidiary ring. The depth d is the number of levels of the recursive appending of subsidiary rings. There are different definitions according to which rings are appended to nodes created at the preceding level (called an HRN) or to any node (called here an HBN for Hierarchical Bubble Network). The case of an HRN was considered by Aiello et al. who give bounds (not tight) on the diameter of such an HRN as a function of the depth and the number of nodes. Here we determine the exact order of the diameter both for an HRN and an HBN. In fact we consider the optimization problem of maximizing the number of nodes of an HBN (or an HRN) of given depth d and diameter D. We reduce the problem to a system of equations with a complex objective function. Solving this system enables us to determine precisely the structure of an optimal HBN and to show that the maximum number of nodes is of order D d /d!.
Published: 2003
Full Text: View/download PDF

21. On Hamilton cycle decompositions of the tensor product of complete graphs

Author: Min-Li Yu, R. Balakrishnan, Jean-Claude Bermond, P. Paulraja, Annamalai University, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (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), 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: Discrete mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Complete graph, Tensor product of Hilbert spaces, Graph theory, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Hamiltonian path, [INFO.INFO-SI]Computer Science [cs]/Social and Information Networks [cs.SI], Theoretical Computer Science, Combinatorics, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], symbols.namesake, Tensor product, Tensor (intrinsic definition), symbols, Discrete Mathematics and Combinatorics, Tensor product of graphs, Decomposition method (constraint satisfaction), Mathematics
Abstract: International audience; In this paper we show that the tensor product of complete graphs is hamilton cycle decomposable.
Published: 2003
Full Text: View/download PDF

22. The power of small coalitions in graphs

Author: David Peleg, Stéphane Pérennes, Jean-Claude Bermond, J. Bond, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (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), and Weizmann Institute of Science [Rehovot, Israël]
Subjects: Combinatorics, Discrete mathematics, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Applied Mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Discrete Mathematics and Combinatorics, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Upper and lower bounds, Graph, [INFO.INFO-SI]Computer Science [cs]/Social and Information Networks [cs.SI], Mathematics, Vertex (geometry)
Abstract: International audience; This paper considers the question of the in uence of a coalition of vertices, seeking to gain control (or majority) in local neighborhoods in a general graph. Say that a vertex v is controlled by the coalition M if the majority of its neighbors are from M. We ask how many vertices (as a function of jMj) can M control in this fashion. Upper and lower bounds are provided for this problem, as well as for cases where the majority is computed over larger neighborhoods (either neighborhoods of some xed radius r 1, or all neighborhoods of radii up to r). In particular, we look also at the case where the coalition must control all vertices (including or excluding its own), and derive bounds for its size.
Published: 2003
Full Text: View/download PDF

23. Design of fault-tolerant networks for satellites (TWTA redundancy)

Author: Jean-Claude Bermond, Eric Darrot, Olivier Delmas, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université 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 Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Computer Networks and Communications, Computer science, satellite, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, Disjoint sets, Traveling-wave tube, Topology, 01 natural sciences, law.invention, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], law, Redundancy (engineering), Commutation, ComputingMilieux_MISCELLANEOUS, TWTA redundancy, Interconnection, 021103 operations research, business.industry, Amplifier, Fault tolerance, routing, 010201 computation theory & mathematics, Hardware and Architecture, connectivity, fault-tolerant networks, Satellite, Telecommunications, business, Software, switching networks, Information Systems
Abstract: This article deals with the design of networks to be placed on satellites. These networks should connect inputs (corresponding to signals arriving at the satellite) to outputs (corresponding to amplifiers, also called Traveling Wave Tube Amplifiers (TWTA)), even in case of failures of amplifiers. The networks are made of links and expensive switches; hence, we want to minimize the number of switches subject to the following conditions: Each input and each output is connected to exactly one switch; each switch is adjacent to exactly four links; there are n inputs and n + k outputs; among the n + k outputs, k can fail permanently; and, finally, all the input signals should be sent to valid amplifiers, that is, outputs, via disjoint paths. So, the aim is to design networks having as few switches as possible and satisfying the following property: There exist n edge-disjoint paths from the n inputs to any set of n outputs chosen from the n + k total number of outputs. We call such networks valid k-fault tolerant networks. Let (n, k) denote the minimum number of switches of a valid network with n inputs, n + k outputs, and k output failures. In this article, we give some details on the problem and some preliminary results such as the fact that (n, k) ≥ n. We also propose a general construction which yields (under some conditions) (n + n′,k) ≤ (n, k) + (n′,k). © 2002 Wiley Periodicals, Inc.
Published: 2002
Full Text: View/download PDF

24. Detection number of bipartite graphs and cubic graphs

Author: Nagarajan Paramaguru, Rathinaswamy Sampathkumar, Frédéric Havet, 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 (... - 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), Mathematics Wing, Directorate of Distance Education [India], Annamalai University, Mathematics Section [India], ANR-09-BLAN-0373,GraTel(2009), 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), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), and INRIA
Subjects: Discrete mathematics, General Computer Science, Foster graph, cubic graph, Neighbourhood (graph theory), bipartite grap, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Gray graph, NP-completeness, Theoretical Computer Science, detectable coloring, Combinatorics, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Edge-transitive graph, Graph power, Bipartite graph, Discrete Mathematics and Combinatorics, Bound graph, Graph toughness, Mathematics
Abstract: For a connected graph G of order |V(G)| ≥ 3 and a k-labelling c : E(G) → {1,2, . . . ,k} of the edges of G, the code of a vertex v of G is the ordered k-tuple (ℓ1, ℓ2, . . . , ℓk), where ℓi is the number of edges incident with v that are labelled i. The k-labelling c is detectable if every two adjacent vertices of G have distinct codes. The minimum positive integer k for which G has a detectable k-labelling is the detection number of G. In this paper, we show that it is NP-complete to decide if the detection number of a cubic graph is 2. We also show that the detection number of every bipartite graph of minimum degree at least 3 is at most 2. Finally, we give some sufficient condition for a cubic graph to have detection number 3.; Pour un graphe connexe G d'ordre |V(G)| ≥ 3 et un étiquetage c : E(G) → {1,2, . . . ,k} des arêtes de G, le code d'un sommet v de G est le k-uplet (ℓ1, ℓ2, . . . , ℓk), où ℓi est le nombre d'arêtes incidentes à v qui sont étiquetées i. Le k-étiquetage c est détectable si, quels que soient deux sommets adjacents de G, leurs codes sont distincts. Le plus petit entier strictement positif k pour lequel G a un k-étiquetage détectable est l'indice de détection det(G) de G. Dans ce rapport, nous montrons qu'il est NP-complet de décider si l'indice de détection d'une graphe cubique vaut 2. Nous montrons également que l'indice de détection de tout graphe biparti de degré minimum au moins 3 est au plus 2. Enfin, nous donnons des conditions suffisantes pour qu'un graphe cubique soit d'indice de détection 3.
Published: 2014
Full Text: View/download PDF

25. Re-routing algorithms in a meshed satellite constellation

Author: Afonso Ferreira, Jérôme Galtier, Jean-Noël Petit, Hervé Rivano, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), France Télécom Recherche & Développement (FT R&D), France Télécom, European RTN ARACNE, INRIA project COMMOBIL, RNRT project Constellation, INRlA-CNPq project 'Communications Mobiles', Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Transmission intersatellite, Computer science, Satellite constellation, Routage réseau, 02 engineering and technology, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], 0203 mechanical engineering, 0202 electrical engineering, electronic engineering, information engineering, Network routing, Electrical and Electronic Engineering, Constellation satellite, Computer communication networks, Service quality, business.industry, Reservation, Routing algorithm, Satellite orbite terrestre basse, 020302 automobile design & engineering, 020206 networking & telecommunications, Réservation, Low earth orbit satellite, business, Telecommunications, Satellite telecommunication, Computer network
Abstract: International audience; In this paper we present a simple model for satellite constellations with polar orbits and inter-satellite links. This model is used to propose and study two algorithms for routing and re-routing communications, which aim at improving the quality of service for long communications. In order to study these algorithms, we have developed a satellite constellation simulator. Some of its results are presented.; Après avoir présenté un modèle de constellation de satellites à orbites polaires et liens intersatellites, nous proposons et étudions deux algorithmes de routage et de reroutage de communications. Ces algorithmes visent à améliorer la qualité de service des communications de longue durée. Pour l’étude de ces algorithmes, nous développons un simulateur de constellation de satellites dont nous présentons quelques résultats.
Published: 2001
Full Text: View/download PDF

26. A quantitative analysis of the capacity of wireless mesh networks

Author: Ioannis G. Fraimis, Vasileios D. Papoutsis, Stavros Kotsopoulos, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), System and Networking for Portable Objects Proved to be Safe (POPS), Laboratoire d'Informatique Fondamentale de Lille (LIFL), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-IRCICA, 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 Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Beamforming, Mathematical optimization, Computer science, Orthogonal frequency-division multiplexing, ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS, 020208 electrical & electronic engineering, 020206 networking & telecommunications, 02 engineering and technology, Computer Science Applications, Many antennas, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Base station, Modeling and Simulation, Telecommunications link, 0202 electrical engineering, electronic engineering, information engineering, Resource allocation, Electrical and Electronic Engineering, Selection (genetic algorithm), Communication channel
Abstract: International audience; Evaluating wireless mesh network performances has become a specific challenge since the emergence of ubiquitous computing. In this article, we consider the network capacity as the performance measure and study its behaviour under two different interference models: (i) usual IEEE 802.11 MAC layer with acknowledgments at each hop, and (ii) block acknowledgments reported at the transport layer that can be included in the IEEE 802.16 standard. We derive a linear program modeling crosslayer characteristics of the wireless mesh network that is solved using column generation. We quantify the capacity gain induced by the move of the MAC acknowledgments into the transport layer, and show that a better load distribution is also obtained.
Published: 2010
Full Text: View/download PDF

27. List circular backbone colouring

Author: Andrew D. King, Frédéric Havet, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Pacific Institute for the Mathematical Sciences (PIMS), University of Calgary, Department of Mathematics [Burnaby] (SFU), Simon Fraser University (SFU.ca), Department of computer science [Burnaby], INRIA, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), 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), Departments of mathematics and computing science, and University of Calgary-Centre National de la Recherche Scientifique (CNRS)
Subjects: Discrete mathematics, Critical graph, General Computer Science, Discrete Mathematics, Graph colouring, General problem, Minimum distance, Graph theory, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Theoretical Computer Science, Combinatorics, Metric space, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Bounded function, Graph Theory, Discrete Mathematics and Combinatorics, Chromatic scale, Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: Graph Theory, A natural generalization of graph colouring involves taking colours from a metric space and insisting that the endpoints of an edge receive colours separated by a minimum distance dictated by properties of the edge. In the q-backbone colouring problem, these minimum distances are either q or 1, depending on whether or not the edge is in the backbone. In this paper we consider the list version of this problem, with particular focus on colours in ℤp - this problem is closely related to the problem of circular choosability. We first prove that the list circular q-backbone chromatic number of a graph is bounded by a function of the list chromatic number. We then consider the more general problem in which each edge is assigned an individual distance between its endpoints, and provide bounds using the Combinatorial Nullstellensatz. Through this result and through structural approaches, we achieve good bounds when both the graph and the backbone belong to restricted families of graphs.
Published: 2014
Full Text: View/download PDF

28. Toward more localized local algorithms: removing assumptions concerning global knowledge

Author: Laurent Viennot, Amos Korman, Jean-Sébastien Sereni, 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), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Laboratory of Information, Network and Communication Sciences (LINCS), 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), 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 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)
Subjects: FOS: Computer and information sciences, Computer Networks and Communications, Computer science, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, Computer Science - Data Structures and Algorithms, 0202 electrical engineering, electronic engineering, information engineering, Data Structures and Algorithms (cs.DS), Probabilistic analysis of algorithms, Pruning (decision trees), Local algorithm, Computer communication networks, Weighted Majority Algorithm, 020206 networking & telecommunications, State (functional analysis), Randomized algorithm, Running time, Computer Science - Distributed, Parallel, and Cluster Computing, Computational Theory and Mathematics, Distributed algorithm, 010201 computation theory & mathematics, Hardware and Architecture, Theory of computation, Distributed, Parallel, and Cluster Computing (cs.DC), Coloring problem, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Algorithm, Pruning (morphology)
Abstract: International audience; Numerous sophisticated local algorithm were suggested in the literature for various fundamental problems. Notable examples are the MIS and (∆+1)-coloring algorithms by Barenboim and Elkin [6], by Kuhn [22], and by Panconesi and Srinivasan [34], as well as the O(∆ 2)-coloring algorithm by Linial [28]. Unfortunately, most known local algorithms (including, in particular, the aforementioned algorithms) are non-uniform, that is, local algorithms generally use good estimations of one or more global parameters of the network, e.g., the maximum degree ∆ or the number of nodes n. This paper provides a method for transforming a non-uniform local algorithm into a uniform one. Furthermore , the resulting algorithm enjoys the same asymp-totic running time as the original non-uniform algorithm. Our method applies to a wide family of both deterministic and randomized algorithms. Specifically, it applies to almost all state of the art non-uniform algorithms for MIS and Maximal Matching, as well as to many results concerning the coloring problem. (In particular, it applies to all aforementioned algorithms.) To obtain our transformations we introduce a new distributed tool called pruning algorithms, which we believe may be of independent interest.
Published: 2013
Full Text: View/download PDF

29. Orchestrating the interoperability workflow within a transport simulation platform

Author: Judicaël Ribault, Gregory Zacharewicz, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (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), Advanced Real-Time Simulation Laboratory (ARS), Carleton University, Laboratoire de l'intégration, du matériau au système (IMS), Université Sciences et Technologies - Bordeaux 1 (UB)-Institut Polytechnique de Bordeaux-Centre National de la Recherche Scientifique (CNRS), 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), and Centre National de la Recherche Scientifique (CNRS)-Institut Polytechnique de Bordeaux-Université Sciences et Technologies - Bordeaux 1
Subjects: [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2013

30. Directed acyclic graphs with the unique dipath property

Author: Stéphane Pérennes, Jean-Claude Bermond, Michel Cosnard, 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 (... - 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), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: DAG (Directed acyclic graphs), General Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], good labelings, chromatic number, 0202 electrical engineering, electronic engineering, information engineering, Maximum size, Mathematics, Discrete mathematics, dipaths, conflict graphs, 020206 networking & telecommunications, load, Directed acyclic graph, intersection graphs, Graph, Vertex (geometry), 010201 computation theory & mathematics, Bounded function, Ordered pair, wavelengths
Abstract: International audience; Let P be a family of dipaths of a DAG (Directed Acyclic Graph) G. The load of an arc is the number of dipaths containing this arc. Let π(G, P) be the maximum of the load of all the arcs and let w(G, P) be the minimum number of wavelengths (colors) needed to color the family of dipaths P in such a way that two dipaths with the same wavelength are arc-disjoint. There exist DAGs such that the ratio between w(G, P) and π(G, P) cannot be bounded. An internal cycle is an oriented cycle such that all the vertices have at least one predecessor and one successor in G (said otherwise every cycle contain neither a source nor a sink of G). We prove that, for any family of dipaths P, w(G, P) = π(G, P) if and only if G is without internal cycle. We also consider a new class of DAGs, which is of interest in itself, those for which there is at most one dipath from a vertex to another. We call these digraphs UPP-DAGs. For these UPP-DAGs we show that the load is equal to the maximum size of a clique of the conflict graph. We prove that the ratio between w(G, P) and π(G, P) cannot be bounded (a result conjectured in an other article). For that we introduce "good labelings" of the conflict graph associated to G and P, namely labelings of the edges such that for any ordered pair of vertices (x, y) there do not exist two paths from x to y with increasing labels.
Published: 2013
Full Text: View/download PDF

31. A unified approach for different tasks on rings in robot-based computing systems

Author: Nicolas Nisse, Karol Suchan, Alfredo Navarra, Gabriele Di Stefano, Gianlorenzo D'Angelo, Dipartimento di Matematica e Informatica [Perugia] (DMI), Università degli Studi di Perugia = University of Perugia (UNIPG), 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), University of L'Aquila [Italy] (UNIVAQ), Inria Chile, Universidad Diego Portales [Santiago] (UDP)-Universidad de la frontera [Chile]-Pontificia Universidad Católica de Chile (UC)-Institut National de Recherche en Informatique et en Automatique (Inria)-Pontificia Universidad Católica de Valparaíso (PUCV)-Universidad Adolfo Ibáñez [Santiago]-Universidad de Valparaiso [Chile]-Universidad Tecnica Federico Santa Maria [Valparaiso] (UTFSM)-Universidad de Concepción - University of Concepcion [Chile], Facultad de Ingeniería y Ciencias [Santiago], Universidad Adolfo Ibáñez [Santiago], Project ECOS-SUD Chile (Action ECOS C12E03) and the Inria Associated Team AlDyNet., Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), 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), Università degli Studi di Perugia (UNIPG), INRIA, Universidad de Valparaiso [Chile]-Universidad Tecnica Federico Santa Maria [Valparaiso] (UTFSM)-Universidad Adolfo Ibáñez [Santiago]-Pontificia Universidad Católica de Valparaíso (PUCV)-Institut National de Recherche en Informatique et en Automatique (Inria)-Pontificia Universidad Católica de Chile (UC)-Universidad de Concepción [Chile]-Universidad de la frontera [Chile]-Universidad Diego Portales [Santiago] (UDP), and Universidad Diego Portales [Santiago] (UDP)-Universidad de la frontera [Chile]-Universidad de Concepción [Chile]-Pontificia Universidad Católica de Chile (UC)-Institut National de Recherche en Informatique et en Automatique (Inria)-Pontificia Universidad Católica de Valparaíso (PUCV)-Universidad Adolfo Ibáñez [Santiago]-Universidad de Valparaiso [Chile]-Universidad Tecnica Federico Santa Maria [Valparaiso] (UTFSM)
Subjects: Personal robot, Social robot, Computer science, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Graph theory, 0102 computer and information sciences, 02 engineering and technology, Motion control, 01 natural sciences, Electronic mail, Computer Science::Robotics, 010201 computation theory & mathematics, Asynchronous communication, 0202 electrical engineering, electronic engineering, information engineering, Graph (abstract data type), Robot, 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: A set of autonomous robots have to collaborate in order to accomplish a common task in a ring-topology where neither nodes nor edges are labeled. We present a unified approach to solve three important problems in the field: the exclusive perpetual exploration, the exclusive perpetual graph searching and the gathering problems. In the first problem, each robot aims at visiting each node infinitely often; in perpetual graph searching, the team of robots aims at clearing all edges of the network infinitely often; and in the gathering problem, all robots must eventually occupy the same node. We investigate these tasks in the famous CORDA distributed computing model where the robots cannot communicate but can perceive the positions of other robots. More precisely, each robot is equipped with visibility sensors and motion actuators, and it operates in Look-Compute-Move asynchronous cycles. Moreover, robots are anonymous, oblivious, uniform and have no common sense of orientation. For the first two problems, the exclusivity constraint must also be satisfied, i.e., a node can be occupied by at most one robot. In this setting, we devise algorithms that, starting from any exclusive rigid (i.e. aperiodic and asymmetric) configuration, solve the three above mentioned problems in anonymous ring-topologies. Besides being a unified approach for three different tasks, the given algorithms solve some open problems. Moreover, we provide some impossibility results for the perpetual graph searching problem.
Published: 2013

32. Feasibility study on distributed simulations of BGP

Author: David Coudert, Aurélien Lancin, Dimitri Papadimitriou, Luc Hogie, Issam Tahiri, Stéphane Pérennes, 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), Bell Labs, Alcatel-Lucent Bell - Belgique, Alacatel Lucent-Alacatel Lucent, Alcatel-Lucent-Bell, European Project: 258307,EC:FP7:ICT,FP7-ICT-2009-5,EULER(2010), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), 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), and Alacatel Lucent
Subjects: FOS: Computer and information sciences, Routing protocol, Computer science, Distributed computing, Routing table, Enhanced Interior Gateway Routing Protocol, Network, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Computer Science - Networking and Internet Architecture, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Distributed Simulation, 0202 electrical engineering, electronic engineering, information engineering, Networking and Internet Architecture (cs.NI), Internet, Static routing, Zone Routing Protocol, business.industry, ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS, BGP, 020206 networking & telecommunications, 010201 computation theory & mathematics, Border Gateway Protocol, Interior gateway protocol, Default-free zone, Discrete event Simulation, business, Computer network
Abstract: The Autonomous System (AS) topology of the Internet (up to 61k ASs) is growing at a rate of about 10% per year. The Border Gateway Protocol (BGP) starts to show its limits in terms of the number of routing table entries it can dynamically process and control. Due to the increasing routing information processing and storage, the same trend is observed for routing model simulators such as DRMSim specialized in large-scale simulations of routing models. Therefore, DRMSim needs enhancements to support the current size of the Internet topology and its evolution (up to 100k ASs). To this end, this paper proposes a feasibility study of the extension of DRMSim so as to support the Distributed Parallel Discrete Event paradigm. We first detail the possible distribution models and their associated communication overhead. Then, we analyze this overhead by executing BGP on a partitioned topology according to different scenarios. Finally, we conclude on the feasibility of such a simulator by computing the expected additional time required by a distributed simulation of BGP compared to its sequential simulation., Comment: 26th ACM/IEEE/SCS Workshop on Principles of Advanced and Distributed Simulation (2012)
Published: 2013

33. Xcast6 Treemap Islands - Revisiting Multicast Model

Author: Cuong Ngoc Tran, Khoa Truong Phan, Joanna Moulierac, Nam Thoai, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Faculty of Mechanical Engineering [HCM University] (FME), Ho Chi Minh City University of Technology (HCMUT), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Overlay multicast, IP Multicast, Overlay Network, Protocol Independent Multicast, Multicast, business.industry, Inter-domain, computer.internet_protocol, Computer science, Distributed computing, ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS, Distance Vector Multicast Routing Protocol, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Source-specific multicast, IP multicast, Xcast, business, computer, Computer network, Xcast6 Treemap islands
Abstract: International audience; Due to the complexity and poor scalability, IP Multicast has not been used on the Internet. Recently, Xcast6 - a complementary protocol of IP Multicast has been proposed. However, the key limitation of Xcast6 is that it only supports small multicast sessions. To overcome this, we propose Xcast6 Treemap islands (X6Ti) - a hybrid model of Overlay Multicast and Xcast6. In summary, X6Ti has many advantages: support large multicast groups, simple and easy to deploy on the Internet, no router configuration, no restriction on the number of groups, no multicast routing protocol and no group management protocol. Based on simulation, we compare X6Ti with IP Multicast and NICE protocols to show the benefits of our new model.
Published: 2012

34. A propos de la difficulté du routage égal par plus courts chemins

Author: Issam, Tahiri, Pérennes, Stéphane, Giroire, Frédéric, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), RAISOM, INRIA, Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Abstract: Les réseaux de communications sont devenus très complexes de nos jours. Cependant, depuis leur tout début avec ARPANET, les chercheurs et les ingénieurs ont conçu plusieurs protocoles aux divers équipements de ces réseaux afin de réduire cette complexité et d'atteindre la meilleure performance possible du réseau. OSPF ("Open Shortest Path First") est l'un des plus anciens protocoles qui ont tenu bon avec cette évolution. Il appartient à la sous-famille des protocoles de routage. Le but d'un protocol de routage est de rendre chaque routeur capable de décider, à chaque paquet recu, le prochain routeur voisin à qui ce paquet doit etre transmis. Quand le protocole de routage activé sur le réseau est OSPF, tout les paquets suivent des plus courts chemins pondérés, ou les poids (à voir comme des longueurs) sont fixés par l'administrateur réseau. Quand ces poids sont définis de manière à avoir plusieurs plus courts chemins pour une paire de noeuds, le routage dépendra de la règle qui est implémentée avec OSPF. Il y a plusieurs règles permettant de balancer le trafic entre les différents plus courts chemins, et l'une des plus connues est ECMP ("Equal Cost Multiple Path"): un noeud qui a plusieurs liens sortant sur le plus court chemin envers une destination d divisera le trafic qui lui arrive et qui est destiné à d de manière égale entre tous les chemins. Si le trafic nécessite de ne pas être partagé entre différents chemins, les poids doivent etre affectés de manière à ce que pour chaque paire de noeuds il y ait un unique plus court chemin. Afin de comprendre la difficulté du routage OSPF, nous avons regardé un problème assez simple, mais qui reste fondamental, où le but est de maximiser le débit quand une seule et unique paire de noeuds com- munique des données sur le réseau. A notre meilleure connaissance, ce problème a été prouvé NP-complet, utilisant une réduction au problème de la couverture d'un ensemble, et aucune approximation, avec garantie non trivial, n'a été proposée jusqu'à présent. Nous montrons, en utilisant une réduction différente que ce problème ne peut être approximée à un facteur constant et nous donnons une approximation qui dépend de la plus longue distance du graphe.
Published: 2012

35. Diverse Routing in Networks with Star SRLGs

Author: Gianlorenzo D'Angelo, Jean-Claude Bermond, David Coudert, Fatima Zahra Moataz, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (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), University of L'Aquila [Italy] (UNIVAQ), Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: 020203 distributed computing, Polynomial, Distributed computing, Node (networking), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 020206 networking & telecommunications, 02 engineering and technology, Shared risk link group, Star (graph theory), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Set (abstract data type), Diverse routing, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], 0202 electrical engineering, electronic engineering, information engineering, Routing (electronic design automation), SRLG, Event (probability theory), Mathematics
Abstract: International audience; The notion of Shared Risk Link Group, SRLG has been intro- duced to capture multiple correlated failures in a network. A SRLG is a set of links that fail simultaneously if a given event (risk) occurs. In such multiple failures scenario, the problem of Diverse Routing consists in finding two SRLG- disjoint paths between a pair of nodes. We consider such problem for localized failures, when all the links of a SRLG verify the star property i.e. when they are incident to the same node. We prove that in this case the problem is in gen- eral NP-complete and determine some polynomial cases.
Published: 2012

36. On reproducibility and traceability of simulations

Author: Dalle, Olivier, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (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), Active objects, semantics, Internet and security (OASIS), C. Laroque and J. Himmelspach and R. Pasupathy and O. Rose and A. M. Uhrmacher, EA DISSIMINET, ANR-11-INFR-0013,SONGS,Simulation de systèmes de prochaine génération(2011), Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: 050210 logistics & transportation, ACM: I.: Computing Methodologies/I.6: SIMULATION AND MODELING, 0502 economics and business, 05 social sciences, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, 02 engineering and technology, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation
Abstract: International audience; Reproducibility of experiments is the pillar of a rigorous scientific approach. However, simulation-based experiments often fail to meet this fundamental requirement. In this paper, we first revisit the definition of reproducibility in the context of simulation. Then, we give a comprehensive review of issues that make this highly desirable feature so difficult to obtain. Given that experimental (in-silico) science is only one of the many applications of simulation, our analysis also explores the needs and benefits of providing the simulation reproducibility property for other kinds of applications. Coming back to scientific applications, we give a few examples of solutions proposed for solving the above issues. Finally, going one step beyond reproducibility, we also discuss in our conclusion the notion of traceability and its potential use in order to improve the simulation methodology.
Published: 2012

37. Complexity of greedy edge-colouring

Author: Havet, Frédéric, Maia de Oliviera, Ana Karolinna, Yu, Min-Li, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Department of Mathematics and Statistics [Fraser Valley], University College of the Fraser Valley (UFV), INRIA, ANR-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: greedy algorithm, Mathematics::Combinatorics, line graphs, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], NP-complete, Edge colouring, caterpillars, greedy colouring
Abstract: The Grundy index of a graph G = (V,E) is the greatest number of colours that the greedy edge-colouring algorithm can use on G. We prove that the problem of determining the Grundy index of a graph G = (V,E) is NP-hard for general graphs. We also show that this problem is polynomial-time solvable for caterpillars. More specifically, we prove that the Grundy index of a caterpillar is $\Delta(G)$ or $\Delta(G)+1$ and present a polynomial-time algorithm to determine it exactly.
Published: 2012

38. On the Grundy number of graphs with few P4's

Author: Júlio Araújo, C. Linhares Sales, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), This work was partially supported by CNPq/Brazil (Projects 479535/2007-8 and 309536/2007-3)., Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Discrete mathematics, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Applied Mathematics, 010102 general mathematics, Graph theory, 0102 computer and information sciences, 01 natural sciences, Graph, Combinatorics, Modular decomposition, Pathwidth, 010201 computation theory & mathematics, Grundy number, Discrete Mathematics and Combinatorics, 0101 mathematics, Greedy algorithm, Time complexity, Mathematics
Abstract: International audience; The Grundy number of a graph G is the largest number of colors used by any execution of the greedy algorithm to color G. The problem of determining the Grundy number of G is polynomial if G is a P4-free graph and NP-hard if G is a P5-free graph. In this article, we define a new class of graphs, the fat-extended P4-laden graphs, and we show a polynomial time algorithm to determine the Grundy number of any graph in this class. Our class intersects the class of P5-free graphs and strictly contains the class of P4-free graphs. More precisely, our result implies that the Grundy number can be computed in polynomial time for any graph of the following classes: P4-reducible, extended P4-reducible, P4-sparse, extended P4-sparse, P4-extendible, P4-lite, P4-tidy, P4-laden and extended P4-laden, which are all strictly contained in the fat-extended P4-laden class.
Published: 2012
Full Text: View/download PDF

39. Gathering asynchronous and oblivious robots on basic graph topologies under the Look -Compute-Move model

Author: D'Angelo, Gianlorenzo, Di Stefano, Gabriele, Navarra, Alfredo, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), University of L'Aquila [Italy] (UNIVAQ), Dipartimento di Matematica e Informatica [Perugia] (DMI), Università degli Studi di Perugia (UNIPG), Steve Alpern and Robbert Fokkink and Leszek Gasieniec and Roy Lindelauf and VS Subrahmanian, 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 Università degli Studi di Perugia = University of Perugia (UNIPG)
Subjects: Computer Science::Robotics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Abstract: Volume dedicated to the Workshop on Search and Rendezvous that took place in May 2012 in Lorentz Centre; International audience; Recent and challenging models of robot-based computing systems consider identical, oblivious and mobile robots placed on the nodes of anonymous graphs. Robots operate asynchronously in order to reach a common node and remain with it. This task is known in the literature as the athering or rendezvous problem. The target node is neither chosen in advance nor marked differently compared to the other nodes. In fact, the graph is anonymous and robots have minimal capabilities. In the context of robot-based computing systems, resources are always limited and precious. Then, the research of the minimal set of assumptions and capabilities required to accomplish the gathering task as well as for other achievements is of main interest. Moreover, the minimality of the assumptions stimulates the investigation of new and challenging techniques that might reveal crucial peculiarities even for other tasks. The model considered in this chapter is known in the literature as the Look-Compute-Move model. Identical robots initially placed at different nodes of an anonymous input graph operate in asynchronous Look-Compute-Move cycles. In each cycle, a robot takes a snapshot of the current global configuration (Look), then, based on the perceived configuration, takes a decision to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case it makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each robot. This means that the time between Look, Compute, and Move operations is finite but unbounded, and it is decided by the adversary for each robot. Hence, robots may move based on significantly outdated perceptions. The only constraint is that moves are instantaneous, and hence any robot performing a Look operation perceives all other robots at nodes of the ring and not on edges. Robots are all identical, anonymous, and execute the same deterministic algorithm. They cannot leave any marks at visited nodes, nor can they send messages to other robots. In this chapter, we aim to survey on recent results obtained for the gathering task over basic graph topologies, that are rings, grids, and trees. Recent achievements to this matter have attracted many researchers, and have provided interesting approaches that might be of main interest to the community that studies robot-based computing systems.
Published: 2012

40. Modeling Sleep Mode Gains in Energy-Aware Networks

Author: Chiaraviglio, Luca, Ciullo, Delia, Mellia, Marco, Meo, Michela, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Models for the performance analysis and the control of networks (MAESTRO), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Department of Electronics [Torino] (DELEN), Politecnico di Torino = Polytechnic of Turin (Polito), INRIA, European Project: 257740,EC:FP7:ICT,FP7-ICT-2009-5,TREND(2010), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Energy-efficient networks, sleep modes, random graph models
Abstract: Nowadays two main approaches are being pursued to reduce energy consumption of networks: the use of sleep modes in which devices enter a low-power state during inactivity periods, and the adoption of energy proportional mechanisms where the device architecture is designed to make energy consumption proportional to the actual load. Common to all the proposals is the evaluation of energy saving performance by means of simulation or experimental evidence, which typically consider a limited set of benchmarking scenarios. In this paper, we do not focus on a particular algorithm or procedure to offer energy saving capabilities in networks, but rather we formulate a theoretical model based on random graph theory that allows to estimate the potential gains achievable by adopting sleep modes in networks where energy proportional devices are deployed. Intuitively, when some devices enter sleep modes some energy is saved. However, this saving could vanish because of the additional load (and power consumption) induced onto the active devices. The impact of this effect changes based on the degree of load proportionality. As such, it is not simple to foresee which are the scenarios that make sleep mode or energy proportionality more convenient. Instead of conducting detailed simulations, we consider simple models of networks in which devices (i.e., nodes and links) consume energy proportionally to the handled traffic, and in which a given fraction of nodes are put into sleep mode. Our model allows to predict how much energy can be saved in different scenarios. The results show that sleep modes can be successfully combined with load proportional solutions. However, if the static power consumption component is one order of magnitude less than the load proportional component, then sleep modes become not convenient anymore. Thanks to random graph theory, our model gauges the impact of different properties of the network topology. For instance, highly connected networks tend to make the use of sleep modes more convenient.
Published: 2012

41. On the Effectiveness of Single and Multiple Base Station Sleep Modes in Cellular Networks

Author: Ajmone Marsan, Marco, Chiaraviglio, Luca, Ciullo, Delia, Meo, Michela, Department of Electronics [Torino] (DELEN), Politecnico di Torino = Polytechnic of Turin (Polito), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Models for the performance analysis and the control of networks (MAESTRO), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), INRIA, European Project: 257740,EC:FP7:ICT,FP7-ICT-2009-5,TREND(2010), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Energy-efficiency, Cellular networks, QoS and sleep modes
Abstract: In this paper we study base station sleep modes that, by reducing power consumption in periods of low traffic, improve the energy efficiency of cellular access networks. We assume that when some base stations enter sleep mode, radio coverage and service provisioning are provided by the base stations that remain active, so as to guarantee that service is available over the whole area at all times. This may be an optimistic assumption in the case of the sparse base station layouts typical of rural areas, but is, on the contrary, a realistic hypothesis for the dense layouts of urban areas, which consume most of the network energy. We consider the possibility of either just one sleep mode scheme per day (bringing the network from a high-power, fully-operational configuration, to a low-power reduced configuration), or several sleep mode schemes per day, with progressively fewer active base stations. For both contexts, we develop a simple analytical framework to identify optimal base station sleep times as a function of the daily traffic pattern. We start by considering homogeneous networks, in which all cells carry the same amount of traffic and cover areas of equal size. Considering both synthetic traffic patterns and real traffic traces, collected from cells of an operational network, we show that the energy saving achieved with base station sleep modes can be quite significant, the actual value strongly depending on the traffic pattern. Our results also show that most of the energy saving is already achieved with one sleep mode scheme per day. Some additional saving can be achieved with multiple sleep mode schemes, at the price of a significant increase in complexity. We then consider heterogeneous networks in which cells with different coverage areas and different amounts of traffic coexist. In particular, we focus on the common case in which some micro-cells provide additional capacity in a region covered by an umbrella macro-cell, and we prove that the optimal scheduling of micro-cell sleep times is in increasing order of load, from the least loaded to the most loaded. This provides a valuable guideline for the scheduling of sleep modes (i.e., of low-power configurations) in complex heterogeneous networks.
Published: 2012

42. Algorithmic aspects of graph colourings heuristics

Author: Sampaio, Leonardo, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Université Nice Sophia Antipolis, and Frédéric Havet(frederic.havet@inria.fr)
Subjects: Fixed Parameter Complexity, Coloration de graphes, NP-complétude, b-colouring, b-coloration, Graph colouring, coloration gloutonne, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], greedy colouring, NP-completeness, Complexité à Paramètre Fixé
Abstract: A proper colouring of a graph is a function that assigns a colour to each vertex with the restriction that adjacent vertices are assigned with distinct colours. Proper colourings are a natural model for many problems, like scheduling, frequency assignment and register allocation. The problem of finding a proper colouring of a graph with the minimum number of colours is a well-known NP-hard problem. In this thesis we study the Grundy number and the b-chromatic number of graphs, two parameters that evaluate some heuristics for finding proper colourings. We start by giving the state of the art of the results about these parameters. Then, we show that the problem of determining the Grundy number of bipartite or chordal graphs is NP-hard, but it is solvable in polynomial time for P5-free bipartite graphs. After, we show that the problem of determining the b-chromatic number of a chordal distance-hereditary graph is NP-hard, and we give polynomial-time algorithms for some subclasses of block graphs, complement of bipartite graphs and P4-sparse graphs. We also consider the fixed-parameter tractability of determining the Grundy number and the b-chromatic number, and in particular we show that deciding if the Grundy number (or the b-chromatic number) of a graph G is at least |V(G)| - k admits an FPT algorithm when k is the parameter. Finally, we consider the computational complexity of many problems related to comparing the b-chromatic number and the Grundy number with various other related parameters of a graph.; Une coloration propre d'un graphe est une fonction qui attribue une couleur à chaque sommet du graphe avec la restriction que 2 sommets voisins ont des couleurs distinctes. Les colorations propres permettent de modéliser des problèmes d'ordonnancement, d'allocation de fréquences ou de registres. Le problème de trouver une coloration propre d'un graphe qui minimise le nombre de couleurs est un problème NP-difficile très connu. Dans cette thèse, nous étudions le nombre de Grundy et le nombre b-chromatique des graphes, deux paramètres qui permettent d'évaluer quelques heuristiques pour le problème de la coloration propre. Nous commençons par dresser un état de l'art des résultats sur ces deux paramètres. Puis, nous montrons que déterminer le nombre de Grundy est NP-difficile sur les graphes bipartis ou cordaux mais polynomial sur le graphes sans P5 bipartis. Ensuite, nous montrons que déterminer le nombre b-chromatique est NP-difficile pour un graphe cordal et distance-héréditaire, et nous donnons des algorithmes polynomiaux pour certaines sous-classes de graphes blocs, complémentaires des graphes bipartis et P4-sparses. Nous considérons également la complexité à paramètre fixé de déterminer le nombre de Grundy (resp. nombre b-chromatique) et en particulier, nous montrons que décider si le nombre de Grundy (ou le nombre b-chromatique) d'un graphe G est au moins |V(G)| - k admet un algorithme FPT lorsque k est le paramètre. Enfin, nous considérons la complexité de nombreux problèmes liés à la comparaison du nombre de Grundy et nombre b-chromatique avec divers autres paramètres d'un graphe.
Published: 2012

43. Aspects algorithmiques d'heuristiques de coloration de graphes

Author: Sampaio, Leonardo, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (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), Université Nice Sophia Antipolis, Frédéric Havet(frederic.havet@inria.fr), Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: Fixed Parameter Complexity, Coloration de graphes, NP-complétude, b-colouring, b-coloration, Graph colouring, coloration gloutonne, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], greedy colouring, NP-completeness, Complexité à Paramètre Fixé
Abstract: A proper colouring of a graph is a function that assigns a colour to each vertex with the restriction that adjacent vertices are assigned with distinct colours. Proper colourings are a natural model for many problems, like scheduling, frequency assignment and register allocation. The problem of finding a proper colouring of a graph with the minimum number of colours is a well-known NP-hard problem. In this thesis we study the Grundy number and the b-chromatic number of graphs, two parameters that evaluate some heuristics for finding proper colourings. We start by giving the state of the art of the results about these parameters. Then, we show that the problem of determining the Grundy number of bipartite or chordal graphs is NP-hard, but it is solvable in polynomial time for P5-free bipartite graphs. After, we show that the problem of determining the b-chromatic number of a chordal distance-hereditary graph is NP-hard, and we give polynomial-time algorithms for some subclasses of block graphs, complement of bipartite graphs and P4-sparse graphs. We also consider the fixed-parameter tractability of determining the Grundy number and the b-chromatic number, and in particular we show that deciding if the Grundy number (or the b-chromatic number) of a graph G is at least |V(G)| - k admits an FPT algorithm when k is the parameter. Finally, we consider the computational complexity of many problems related to comparing the b-chromatic number and the Grundy number with various other related parameters of a graph.; Une coloration propre d'un graphe est une fonction qui attribue une couleur à chaque sommet du graphe avec la restriction que 2 sommets voisins ont des couleurs distinctes. Les colorations propres permettent de modéliser des problèmes d'ordonnancement, d'allocation de fréquences ou de registres. Le problème de trouver une coloration propre d'un graphe qui minimise le nombre de couleurs est un problème NP-difficile très connu. Dans cette thèse, nous étudions le nombre de Grundy et le nombre b-chromatique des graphes, deux paramètres qui permettent d'évaluer quelques heuristiques pour le problème de la coloration propre. Nous commençons par dresser un état de l'art des résultats sur ces deux paramètres. Puis, nous montrons que déterminer le nombre de Grundy est NP-difficile sur les graphes bipartis ou cordaux mais polynomial sur le graphes sans P5 bipartis. Ensuite, nous montrons que déterminer le nombre b-chromatique est NP-difficile pour un graphe cordal et distance-héréditaire, et nous donnons des algorithmes polynomiaux pour certaines sous-classes de graphes blocs, complémentaires des graphes bipartis et P4-sparses. Nous considérons également la complexité à paramètre fixé de déterminer le nombre de Grundy (resp. nombre b-chromatique) et en particulier, nous montrons que décider si le nombre de Grundy (ou le nombre b-chromatique) d'un graphe G est au moins |V(G)| - k admet un algorithme FPT lorsque k est le paramètre. Enfin, nous considérons la complexité de nombreux problèmes liés à la comparaison du nombre de Grundy et nombre b-chromatique avec divers autres paramètres d'un graphe.
Published: 2012

44. (Circular) backbone colouring: tree backbones in planar graphs

Author: Havet, Frédéric, King, Andrew, Liedloff, Mathieu, Todinca, Ioan, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (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), Department of Mathematics [Burnaby] (SFU), Simon Fraser University (SFU.ca), Department of computer science [Burnaby], Laboratoire d'Informatique Fondamentale d'Orléans (LIFO), Université d'Orléans (UO)-Ecole Nationale Supérieure d'Ingénieurs de Bourges, INRIA, ANR-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009), 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), and Ecole Nationale Supérieure d'Ingénieurs de Bourges-Université d'Orléans (UO)
Subjects: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract: Consider an undirected graph G and a subgraph H of G, on the same vertex set. The q-backbone chromatic number BBCq(G,H) is the minimum k such that G can be properly coloured with colours from {1, ..., k}, and moreover for each edge of H, the colours of its ends differ by at least q. In this paper we focus on the case when G is planar and H is a forest. We give a series of NP-hardness results as well as upper bounds for BBCq(G,H), depending on the type of the forest (matching, galaxy, spanning tree). Eventually, we discuss a circular version of the problem.; On considère un graphe G (non-orienté) et un sous-graphe H de G. Le nombre chromatique q-dorsal BBCq(G,H) est le plus petit entier k tel que G puisse être coloré proprement avec les couleurs {1, ...,k} de telle sorte qu'en plus pour toute arête de H, les couleurs de ses deux extrémités diff'erent d'au moins q. Dans ce rapport, nous étudions le cas où G est planaire et H est une forêt. Nous donnons une série de résultats de NP-complétude ainsi que des bornes supérieures pour BBCq(G,H), suivant le type de forêt (couplage, galaxie, arbre couvrant). Nous abordons également une version circulaire du problème.
Published: 2012

45. Backbone colouring: tree backbones with small diameter in planar graphs

Author: Campos, Victor, Havet, Frédéric, Sampaio, Rudini, Silva, Ana, Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (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), INRIA, Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract: Given a graph $G$ and a spanning subgraph $T$ of $G$, a {\it backbone $k$-colouring} for $(G,T)$ is a mapping $c:V(G)\to\{1,\ldots,k\}$ such that $|c(u)-c(v)|\geq 2$ for every edge $uv\in E(T)$ and $|c(u)-c(v)|\geq 1$ for every edge $uv\in E(G)\setminus E(T)$. The {\it backbone chromatic number} $BBC(G,T)$ is the smallest integer $k$ such that there exists a backbone $k$-colouring of $(G,T)$. In 2007, Broersma et al. \cite{BFG+07} conjectured that $BBC(G,T)\leq 6$ for every planar graph $G$ and every spanning tree $T$ of $G$. In this paper, we prove this conjecture when $T$ has diameter at most four.; Pour un graphe $G$ et un sous-graphe $T$ de $G$, une {\it $k$-coloration dorsale} de $(G,T)$ est une application $c:V(G)\to\{1,\ldots,k\}$ telle que $|c(u)-c(v)|\geq 2$ pour tout arête $uv\in E(T)$ et $|c(u)-c(v)|\geq 1$ pour toute arête $uv\in E(G)\setminus E(T)$. Le {\it nombre chromatique dorsal} $BBC(G,T)$ est le plus petit entier $k$ tel qu'il existe une $k$-coloration dorsale de $(G,T)$. En 2007, Broersma et al. \cite{BFG+07} ont conjecturé que $BBC(G,T)\leq 6$ pour tout graphe planaire $G$ et tout arbre couvrant $T$ de $G$. Dans ce rapport, nous montrons cette conjecture lorsque $T$ est de diamétre au plus 4.
Published: 2012

46. Internet et la théorie des graphes

Author: Bermond, Jean-Claude, Moulierac, Joanna, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-WB]Computer Science [cs]/Web, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract: National audience; La théorie des graphes constitue un domaine des mathématiques qui s'est développé au sein de disciplines diverses telles que la chimie (modélisation de structures), la biologie (génome), les sciences sociales (modélisation des relations) et le transport (réseaux routiers, électriques, etc.). Le cycle eulérien et le cycle hamiltonien Réseaux internet et graphes " petit-monde " Comment calculer un plus court chemin ?
Published: 2012

47. Exact and approximate algorithms for computing the hyperbolicity of large-scale graphs

Author: Cohen, Nathann, Coudert, David, Lancin, Aurélien, Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (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), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), INRIA, ANR-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009), European Project: 258307,EC:FP7:ICT,FP7-ICT-2009-5,EULER(2010), 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), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), 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), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Hyperbolicity, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], algorithm, exact, graph, approximation
Abstract: Let G be a connected graph, and let d(a, b) denotes the shortest path distance between vertices a and b of G. The graph G is δ-hyperbolic if for any vertices a, b, c, d of G, the two largest of the three sums S1 = d(a,b) + d(c,d), S2 = d(a,c) + d(b,d), and S3 = d(a,d) + d(b,c) differ by at most 2δ. This can be determined in time O(n^4) which could be prohibitive for large graphs. In this document, we propose an exact algorithm for determining the hyperbolicity of a graph that is scalable for large graphs. The time complexity of this algorithm is a function of the size of the largest bi-connected component of the graph, of the shortest path distance distribution in this component and of the value of the hyperbolicity. In the worst case, the time complexity remains in O(n^4), but it is much faster in practice. Indeed, it allowed us to compute the exact hyperbolicity of all maps of the autonomous systems of the Internet provided by CAIDA and DIMES. We also propose both a multiplicative factor and an additive constant approximation algorithms. Finally, we also analyze further the time complexity of our exact algorithm for several class of graphs.; Soit G un graphe connexe et soit d(a, b) la distance entre les sommets a et b dans le graphe. Le graphe G est dit δ-hyperbolic si pour tout quadruplet a, b, c, d de sommets d G, les deux plus grandes des sommes S1 = d(a, b)+d(c, d), S2 = d(a, c)+d(b, d), et S3 = d(a, d)+d(b, c) diffèrent d'au plus 2δ. Cette valeur peut être déterminé en temps O(n^4), ce qui est souvent inaccessible pour les grands graphes. Nous proposons un nouvel algorithme exact pour calculer l'hyperbolicité sur des graphes de grande taille. La complexité en temps de cet algorithme est fonction de la taille de la plus grande composante bi-connexe du graphe, de la distribution des plus courts chemins dans cette composante et de la valeur de l'hyperbolicité. Dans le pire cas, cet algorithme prendra un temps en O(n^4). Cependant, l'algorithme est bien plus efficace en pratique. Il nous a en effet permis de calculé la valeur exacte de l'hyperbolicité pour l'ensemble des cartes Internet CAIDA et DIMES. Nous proposons également un algorithme approché avec un facteur multiplicatif ou avec une constante additive donné en entrée. Enfin, nous analysons la complexité temporelle de notre algorithme pour des classes particulières de graphes.
Published: 2012

48. Energy Saving in Optical Operator Networks: the Challenges, the TREND Vision, and Some Results

Author: Esther Le Rouzic, Luca Chiaraviglio, Felipe Jimenez, Filip Idzikowski, Raul Duque, Marco Ajmone Marsan, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Technische Universität Berlin (TU), Telefonica Investigación y Desarrollo (Telefonica I+D), Telefonica Group, Orange Labs [Issy les Moulineaux], France Télécom, Department of Electronics [Torino] (DELEN), Politecnico di Torino = Polytechnic of Turin (Polito), European Project: 257740,EC:FP7:ICT,FP7-ICT-2009-5,TREND(2010), 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 Technical University of Berlin / Technische Universität Berlin (TU)
Subjects: Engineering, QA Mathematics::QA75 Electronic computers. Computer science [Q Science], Computer Networks and Communications, T Technology (General) [T Technology], Real-time computing, 02 engineering and technology, Network interface, Adaptive routing, 01 natural sciences, 010309 optics, 020210 optoelectronics & photonics, Operator (computer programming), Q Science (General) [Q Science], Wavelength-division multiplexing, 0103 physical sciences, 0202 electrical engineering, electronic engineering, information engineering, Simulation, TA Engineering (General). Civil engineering (General) [T Technology], business.industry, ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS, Networking hardware, Power (physics), Energy conservation, TK Electrical engineering. Electronics Nuclear engineering [T Technology], business, Energy (signal processing)
Abstract: International audience; We discuss how to save energy in IP-over-WDM networks, presenting the vision of TREND, the FP7 NoE, and the saving that can be obtained with an adaptive routing solution that puts network interfaces of various granularities to sleep in periods of low traffic. Results refer to two operator networks, considering power and traffic forecasts for 2020.
Published: 2012

49. Graph Coloring and Graph Convexity

Author: Araujo, Julio, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (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), Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), Université Nice Sophia Antipolis, Jean-Claude Bermond(jean-claude.bermond@inria.fr), Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Convexity, Convexité, Computational Complexity, Coloration, Théorie des Graphes, Graph Theory, Coloring, Complexité
Abstract: In this thesis, we study several problems of Graph Theory concerning Graph Coloring and Graph Convexity. Most of the results contained here are related to the computational complexity of these problems for particular graph classes. In the rst and main part of this thesis, we deal with Graph Coloring which is one of the most studied areas of Graph Theory. We rst consider three graph coloring problems called Greedy Coloring, Weighted Coloring and Weighted Improper Coloring. Then, we deal with a decision problem, called Good Edge-Labeling, whose de nition was motivated by the Wavelength Assignment problem in optical networks. The second part of this thesis is devoted to a graph optimization parameter called (geodetic) hull number. The de nition of this parameter is motivated by an extension to graphs of the notions of convex sets and convex hulls in the Euclidean space. Finally, we present in the appendix other works developed during this thesis, one about Eulerian and Hamiltonian directed hypergraphs and the other concerning distributed storage systems.; Dans cette thèse, nous étudions plusieurs problèmes de théorie des graphes concernant la coloration et la convexité des graphes. La plupart des résultats gurant ici sont liés à la complexité de calcul de ces problèmes pour certaines classes de graphes. Dans la première, et principale, partie de cette thèse, nous traitons de coloration des graphes qui est l'un des domaines les plus étudiés de théorie des graphes. Nous considérons d'abord trois problèmes de coloration appelés coloration gloutone, coloration pondérée et coloration pondérée impropre. Ensuite, nous traitons un probl ème de décision, appelé bon étiquetage de arêtes, dont la dé nition a été motivée par le problème d'affectation de longueurs d'onde dans les réseaux optiques. La deuxième partie de cette thèse est consacrée à un paramètre d'optimisation des graphes appelé le nombre enveloppe (géodésique). La dé nition de ce paramètre est motivée par une extension aux graphes des notions d'ensembles et d'enveloppes convexes dans l'espace Euclidien. En n, nous présentons dans l'annexe d'autres travaux développées au cours de cette thèse, l'un sur les hypergraphes orientés Eulériens et Hamiltoniens et l'autre concernant les systèmes de stockage distribués.
Published: 2012

50. Coloration et convexité dans les graphes

Author: Araujo, Julio, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), Université Nice Sophia Antipolis, and Jean-Claude Bermond(jean-claude.bermond@inria.fr)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Convexity, Convexité, Computational Complexity, Théorie des Graphes, Coloration, Graph Theory, Coloring, Complexité
Abstract: In this thesis, we study several problems of Graph Theory concerning Graph Coloring and Graph Convexity. Most of the results contained here are related to the computational complexity of these problems for particular graph classes. In the rst and main part of this thesis, we deal with Graph Coloring which is one of the most studied areas of Graph Theory. We rst consider three graph coloring problems called Greedy Coloring, Weighted Coloring and Weighted Improper Coloring. Then, we deal with a decision problem, called Good Edge-Labeling, whose de nition was motivated by the Wavelength Assignment problem in optical networks. The second part of this thesis is devoted to a graph optimization parameter called (geodetic) hull number. The de nition of this parameter is motivated by an extension to graphs of the notions of convex sets and convex hulls in the Euclidean space. Finally, we present in the appendix other works developed during this thesis, one about Eulerian and Hamiltonian directed hypergraphs and the other concerning distributed storage systems.; Dans cette thèse, nous étudions plusieurs problèmes de théorie des graphes concernant la coloration et la convexité des graphes. La plupart des résultats gurant ici sont liés à la complexité de calcul de ces problèmes pour certaines classes de graphes. Dans la première, et principale, partie de cette thèse, nous traitons de coloration des graphes qui est l'un des domaines les plus étudiés de théorie des graphes. Nous considérons d'abord trois problèmes de coloration appelés coloration gloutone, coloration pondérée et coloration pondérée impropre. Ensuite, nous traitons un probl ème de décision, appelé bon étiquetage de arêtes, dont la dé nition a été motivée par le problème d'affectation de longueurs d'onde dans les réseaux optiques. La deuxième partie de cette thèse est consacrée à un paramètre d'optimisation des graphes appelé le nombre enveloppe (géodésique). La dé nition de ce paramètre est motivée par une extension aux graphes des notions d'ensembles et d'enveloppes convexes dans l'espace Euclidien. En n, nous présentons dans l'annexe d'autres travaux développées au cours de cette thèse, l'un sur les hypergraphes orientés Eulériens et Hamiltoniens et l'autre concernant les systèmes de stockage distribués.
Published: 2012

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

492 results on '"Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE)"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources