Search

We present our work on the dimensioning of a packet-switching wavelength division multiplexing ring in order to reduce its infrastructure (capital expenditure) cost. We study a new all-optical architecture: the packed optical add-drop multiplexer (POADM). We aim to minimize the overall cost of the network by reducing the number of indispensable devices in the nodes and the number of required wavelengths. We formalize the packing problems underlying the ring dimensioning. The elements to be packed are made up of transmissions that share the same destination. We assume that elements can be cut before being packed into boxes. We furnish a complete theoretical analysis of the complexity and approximability of these problems. We define also several measures of quality for a cut and provide an optimal cutting strategy, according to these measures. Our subsequent contribution is a heuristic solution that solves the bi-criteria packing problem (the number of boxes and the number of cuts are minimized simultaneously). The exhaustive numerical results of this heuristic algorithm come next. We rely on our optimal cutting strategy to appraise the efficiency of other strategies. We also adapt the only existing POADM dimensioning algorithm, more restrictive than ours, and we confront it with our solution. The analysis of results allows us to provide network design guidelines to perform the dimensioning in the most efficient way. [ABSTRACT FROM AUTHOR]

Abstract: A -vertex graph is said to be decomposable if, for any partition of the integer , there exists a sequence of connected vertex-disjoint subgraphs with . The aim of the paper is to study the homeomorphism classes of decomposable trees. More precisely, we show that homeomorphism classes containing decomposable trees with an arbitrarily large minimal distance between all pairs of distinct vertices of degree different from 2, is exactly the set of combs. [Copyright &y& Elsevier]

In the context of an eco-responsible production and distribution of electrical energy at the local scale of an urban territory, we consider a smart grid as a system interconnecting different prosumers, which all retain their decision-making autonomy and defend their own interests in a comprehensive system where the rules, accepted by all, encourage virtuous behavior. In this paper, we present and analyze a model and a management method for smart grids that is shared between different kinds of independent actors, who respect their own interests, and that encourages each actor to behavior that allows, as much as possible, an energy independence of the smart grid from external energy suppliers. We consider here a game theory model, in which each actor of the smart grid is a player, and we investigate distributed machine-learning algorithms to allow decision-making, thus, leading the game to converge to stable situations, in particular to a Nash equilibrium. We propose a Linear Reward Inaction algorithm that achieves Nash equilibria most of the time, both for a single time slot and across time, allowing the smart grid to maximize its energy independence from external energy suppliers. [ABSTRACT FROM AUTHOR]

Abstract: We study the following problem: given a biological sequence S, a multiset of motifs and an integer k, generate uniformly random sequences which contain the given motifs and have exactly the same frequencies of occurrence of k-lets (i.e. factors of length k) of S. We notably prove that the problem of deciding whether a sequence respects the given motif constraints is NP-complete. Nevertheless, we give a random generation algorithm which turns out to be experimentally efficient. [Copyright &y& Elsevier]

Abstract: This paper deals with b-colorings of a graph G, that is, proper colorings in which for each color c, there exists at least one vertex colored by c such that its neighbors are colored by each other color. The b-chromatic number of a graph G is the maximum number of colors for which G has a b-coloring. It is easy to see that every graph G has a b-coloring using colors. We say that G is b-continuous iff for each k, , there exists a b-coloring with k colors. It is well known that not all graphs are b-continuous. We call b-spectrum of G to be the set of integers k for which there is a b-coloring of G by k colors. We show that for any finite integer set I, there exists a graph whose b-spectrum is I and we investigate the complexity of the problem of deciding whether a graph G is b-continuous, even if b-colorings using and colors are given. [Copyright &y& Elsevier]

Abstract: A n-vertex graph is said to be decomposable if for any partition of the integer n, there exists a sequence of connected vertex-disjoint subgraphs with . In this paper, we focus on decomposable trees. We show that a decomposable tree has degree at most 4. Moreover, each degree-4 vertex of a decomposable tree is adjacent to a leaf. This leads to a polynomial time algorithm to decide if a multipode (a tree with only one vertex of degree greater than 2) is decomposable. We also exhibit two families of decomposable trees: arbitrary large trees with one vertex of degree 4, and trees with an arbitrary number of degree-3 vertices. [Copyright &y& Elsevier]

In this paper we deal with global communication schemes such as broadcasting or multicasting, in a packet (sub)network in which each node participates in the same distributed application. We want the communication scheme to be performed periodically as often as possible and with some bandwidth guarantee. Such periodicity properties are needed, for example, by multimedia and grid computation applications. We consider commuted switches in the network, i.e., each outgoing link of the switch is assigned to at most one incoming link. Each switch avoids intermediate buffering. Given a network G and a global communication scheme S, an algorithm performing S in G consists in commuting each switch and in specifying to each emitting node the infinite sequence of steps at which it will send a message. The period of this algorithm is the greatest number of steps between two messages emitted by a node. The window of the algorithm is the maximal number of steps needed by a message to reach its destination(s). We first give a general definition of the model of network we consider and of the global communication schemes we study, i.e., the many-to-all scheme where many nodes have one message to send to all the other ones. One well-known case of the many-to-all scheme we especially focus on is gossiping. We present a general way of periodically performing these communication schemes, by covering the graph by substructures called octopuses. Then we show that optimizing the period and the window are two different problems. We end by giving some examples of applications in the torus network. [ABSTRACT FROM AUTHOR]

In this paper, we focus on convergence packet routing techniques in an all-optical network, obtained from an Eulerian routing in the digraph modeling the target network. Given an Eulerian circuit C in a digraph C, we deal with the maximal number diamWC of arcs that a packet has to follow on C from its origin to its destination (we talk about the ending guarantee of the routing). We consider the Eulerian diameter of C as defined by E(C) = mm C ∈ Eul(G) diamWc, where E(G) is the set of all the Eulerian circuits in C. After giving a preliminary result about the complexity of finding ((C) for any digraph G, we give some lower and upper bounds of this parameter. The main part of the paper is devoted to the description of a combinatorial design of various network topologies having good Eulerian diameters. [ABSTRACT FROM AUTHOR]

This paper reviews some of the graph theory-based methods that were recently developed in our group for post-processing molecular dynamics trajectories. We show that the use of algorithmic graph theory not only provides a direct and fast methodology to identify conformers that are sampled over time, but it also allows to follow in time the interconversions between the conformers through graphs of transitions, also provides statistical characterisations, that would otherwise be hard to obtain. Examples for a gas phase peptide and for the more complex inhomogeneous charged air–liquid water interface are presented in order to demonstrate the power of topological 2D-graphs and their versatility and transferability. [ABSTRACT FROM AUTHOR]

This paper reviews graph-theory-based methods that were recently developed in our group for post-processing molecular dynamics trajectories. We show that the use of algorithmic graph theory not only provides a direct and fast methodology to identify conformers sampled over time but also allows to follow the interconversions between the conformers through graphs of transitions in time. Examples of gas phase molecules and inhomogeneous aqueous solid interfaces are presented to demonstrate the power of topological 2D graphs and their versatility for post-processing molecular dynamics trajectories. An even more complex challenge is to predict 3D structures from topological 2D graphs. Our first attempts to tackle such a challenge are presented with the development of game theory and reinforcement learning methods for predicting the 3D structure of a gas-phase peptide. [ABSTRACT FROM AUTHOR]

In this contribution, we have explored the potential and strength of one-dimensional (1D) 29 Si and two-dimensional (2D) 29S– 29 Si and 29Si– 17O NMR as invariants of non-oriented graph for fingerprinting zeolite frameworks. 1D and 2D 29 Si NMR can indeed provide indications on the graph vertices, edges and allow the construction of the adjacency matrix, i.e. the set of connections between the graph vertices. From the structural data, hypothetical 1D 29Si and 2D 29 Si– 29 Si NMR signatures for 193 of the zeolite frameworks reported in the Atlas of Zeolite Structures have been generated. Comparison between all signatures shows that thanks to the 1D 29 Si NMR data only, almost 20% of the known zeolite frameworks could be distinguished. Further NMR signatures were generated by taking into account 2D 29 Si– 29 Si and 29 Si– 17 O correlations. By sorting and comparison of all the NMR data, up to 80% of the listed zeolites could be unambiguously discriminated. This work indicates that (i) solid-state NMR data indeed represent a rather strong graph invariant for zeolite framework, (ii) despite their difficulties and costs (isotopic labeling is often required, the NMR measurements can be long), 29 Si and 17 O NMR measurements are worth being investigated in the frame of zeolites structure resolution. This approach could also be generalized to other zeolite-related materials containing NMR-measurable nuclides. [ABSTRACT FROM AUTHOR]

Some of our recent developments and applications of algorithmic graph theory for extracting the physical and chemical properties of materials from molecular dynamics simulations are presented. From the chemical viewpoint, the power of graph theory is illustrated in the search for a catalyst's active sites at a silica solid surface. From the physical viewpoint, we present graph algorithms that recognize the structural motifs that exist at the silica/liquid water interface. Statistical analyses of the instances of these surface-water motifs provide a detailed understanding of the structures and dynamics at the aqueous interface.

Improving energy efficiency in the building sector is a subject of significant interest, considering the environmental impact of buildings. Energy efficiency involves many aspects, such as occupant comfort, system monitoring and maintenance, data treatment, instrumentation… Physical modeling and calibration, or artificial intelligence, are often employed to explore these different subjects and, thus, to limit energy consumption in buildings. Even though these techniques are well-suited, they have one thing in common, i.e., the need for user cases. This is why we propose to share a part of the large volume of data collected on our modular education building. The building is located on Nanterre's CESI Engineering school campus and welcomes approximately 80 students daily. A network of more than 150 sensors and actuators allows monitoring of the physical behavior of the entire building, preserving optimal comfort and energy consumption. The dataset includes the indoor physical parameters and the operating conditions of each system to describe the physical behavior of the building during a year., (© 2024 The Authors.)

A novel approach based on a coarse-grained representation of topological graphs is proposed for the automatic analysis of molecular dynamics (MD) trajectories of hydrogen-bonded (H-Bonded) flexible biomolecules. Herein, our approach models an H-Bonded biomolecule by its H-Bonded cycles and its graph of cycles in which the vertices and links represent the intersections between these cycles. We propose a methodology in which each identified conformer/isomer from the MD is represented by a well-chosen set of H-Bonded cycles called a minimum cycle basis. The key component is the "polycycles" that distinguish the cycles that play the same polymorphic role in the molecule from the ones that lead to an actual conformational change of the molecule. The relevance of our proposed method is evaluated on MD trajectories of gas-phase biomolecules, for which the covalent bonds are unchanged over time and only the hydrogen bonds change over time. The polygraphs and their time evolution are shown to reveal the dynamicity of the metastructure(s) of the H-Bonded biomolecules while providing polymorphic information on the cycles. Such information on the dynamics and changes in the H-bond network, as some cycles change identity while retaining the same role in the overall structure, is not easily captured at the atomic level of representation. Such information can instead be captured by polymorphic cycles.

We present an algorithm for automatically predicting the topological family of any RNA three-way junction, given only the information from the secondary structure: the sequence and the Watson-Crick pairings. The parameters of the algorithm have been determined on a data set of 33 three-way junctions whose 3D conformation is known. We applied the algorithm on 53 other junctions and compared the predictions to the real shape of those junctions. We show that the correct answer is selected out of nine possible configurations 64% of the time. Additionally, these results are noticeably improved if homology information is used. The resulting software, Cartaj, is available online and downloadable (with source) at: http://cartaj.lri.fr., (Copyright © 2011 Elsevier Ltd. All rights reserved.)