Search

A line digraph $L(G) = (A, E)$ is the digraph constructed from the digraph $G = (V, A)$ such that there is an arc $(a,b)$ in $L(G)$ if the terminal node of $a$ in $G$ is the initial node of $b$. The maximum number of arcs in a line digraph with $m$ nodes is $(m/2)^2 + (m/2)$ if $m$ is even, and $((m - 1)/2)^2 + m - 1$ otherwise. For $m \geq 7$, there is only one line digraph with as many arcs if $m$ is even, and if $m$ is odd, there are two line digraphs, each being the transpose of the other.

We address a specific case of the matroid intersection problem: given a set of graphs sharing the same set of vertices, select a minimum cycle basis for each graph to maximize the size of their intersection. We provide a comprehensive complexity analysis of this problem, which finds applications in chemoinformatics. We establish a complete partition of subcases based on intrinsic parameters: the number of graphs, the maximum degree of the graphs, and the size of the longest cycle in the minimum cycle bases. Additionally, we present results concerning the approximability and parameterized complexity of the problem.

We address the problem of configuring a power distribution network with reliability and resilience objectives by satisfying the demands of the consumers and saturating each production source as little as possible. We consider power distribution networks containing source nodes producing electricity, nodes representing electricity consumers and switches between them. Configuring this network consists in deciding the orientation of the links between the nodes of the network. The electric flow is a direct consequence of the chosen configuration and can be computed in polynomial time. It is valid if it satisfies the demand of each consumer and capacity constraints on the network. In such a case, we study the problem of determining a feasible solution that balances the loads of the sources, that is their production rates. We use three metrics to measure the quality of a solution: minimizing the maximum load, maximizing the minimum load and minimizing the difference of the maximum and the minimum loads. This defines optimization problems called respectively min-M, max-m and min-R. In the case where the graph of the network is a tree, it is known that the problem of building a valid configuration is polynomial. We show the three optimization variants have distinct properties regarding the theoretical complexity and the approximability. Particularly, we show that min-M is polynomial, that max-m is NP-Hard but belongs to the class FPTAS and that min-R is NP-Hard, cannot 1 be approximated to within any exponential relative ratio but, for any $\epsilon$ > 0, there exists an algorithm for which the value of the returned solution equals the value of an optimal solution shifted by at most $\epsilon$., Comment: Journal of Global Optimization, 2023

The N-GREEN project has for goal to design a low cost optical ring technology with good performances (throughput, latency...) without using expensive end-to-end connections. We study the compatibility of such a technology with the development of the Cloud RAN, a latency critical application which is a major aspect of 5G deployment. We show that deterministically managing Cloud RAN traffic minimizes its latency while also improving the latency of the other traffics.

In order to define the process of restrosynthesis of a new organic molecule, it is often necessary to be able to draw inspiration from that of a molecule similar to the target one of which we know such a process. To compute such a similarity, an oftently used approach is to solve a Maximum Common Edge Subgraph (MCES) problem on molecular graphs, but such an approach is limited by computation time and pertinence of similarity measurement. In this paper, we define and analyse here a new graph representation of molecules to algorithmically compare them. The purpose is to model the structure of molecule by a graph smaller than the molecular graph and representing the interconnexion of its elementary cycles. We provide an algorithm to efficiently obtain such a graph of cycles from a molecular graph. Then by solving MCES problems on those graphs, we evaluate the pertinence of using graphs of cycles for molecular similarity on a select set of molecules., Comment: 32 pages, 40 figures

A recent trend in mobile networks is to centralize in distant data-centers the processing units which were attached to antennas until now. The main challenge is to guarantee that the latency of the periodic messages sent from the antennas to their processing units and back, fulfills protocol time constraints. We show that traditional statistical multiplexing does not allow such a low latency, due to collisions and buffering at nodes. Hence, we propose in this article to use a deterministic scheme for sending periodic messages without collisions in the network thus saving the latency incurred by buffering. We give several algorithms to compute such schemes for a common topology where one link is shared by all antennas. We show that there is always a solution when the routes are short or the load is small. When the parameters are unconstrained, and some buffering is allowed in the processing units, we propose an algorithm (PMLS) adapted from a classical scheduling method. The experimental results show that even under full load, most of the time PMLS finds a deterministic sending scheme with no latency., Comment: 40 pages, 23 Figures

Multi-layer networks are networks in which several protocols may coexist at different layers. The Pseudo-Wire architecture provides encapsulation and de-capsulation functions of protocols over Packet-Switched Networks. In a multi-domain context, computing a path to support end-to-end services requires the consideration of encapsulation and decapsulation capabilities. It appears that graph models are not expressive enough to tackle this problem. In this paper, we propose a new model of heterogeneous networks using Automata Theory. A network is modeled as a Push-Down Automaton (PDA) which is able to capture the encapsulation and decapsulation capabilities, the PDA stack corresponding to the stack of encapsulated protocols. We provide polynomial algorithms that compute the shortest path either in hops or in the number of encapsulations and decapsulations along the inter-domain path, the latter reducing manual configurations and possible loops in the path., Comment: Journal on Computer Communications, 2013

In this paper we describe an algorithm which generates all colored planar maps with a good minimum sparsity from simple motifs and rules to connect them. An implementation of this algorithm is available and is used by chemists who want to quickly generate all sound molecules they can obtain by mixing some basic components., Comment: 17 pages, 7 figures. Accepted at the 14th International Symposium on Experimental Algorithms (SEA 2015)

Dans ce travail, nous montrons comment mettre en oeuvre la gestion des ressources et la garantie de QoS (Quality of Service) dans l'interdomaine en utilisant le mod\`ele en stock. Nous avons d\'ej\`a appliqu\'e un mod\`ele distribu\'e pour l'\'etablissement des SLAs (Service Level Agreement) entre les op\'erateurs pour l'achat des routes avec une garantie de QoS et des r\'esultats significatifs ont \'et\'e obtenus sur des topologies simples. Dans ce travail, nous appliquons un mod\`ele de jeu pour l'\'etablissement des SLAs., Comment: 2 pages, conf\'erence ROADEF'2012

We present a general setting for structure-sequence comparison in a large class of RNA structures that unifies and generalizes a number of recent works on specific families on structures. Our approach is based on tree decomposition of structures and gives rises to a general parameterized algorithm, where the exponential part of the complexity depends on the family of structures. For each of the previously studied families, our algorithm has the same complexity as the specific algorithm that had been given before., Comment: (2012)

The new model that we present in this paper is introduced in the context of guaranteed QoS and resources management in the inter-domain routing framework. This model, called the stock model, is based on a reverse cascade approach and is applied in a distributed context. So transit providers have to learn the right capacities to buy and to stock and, therefore learning theory is applied through an iterative process. We show that transit providers manage to learn how to strategically choose their capacities on each route in order to maximize their benefits, despite the very incomplete information. Finally, we provide and analyse some simulation results given by the application of the model in a simple case where the model quickly converges to a stable state., Comment: 19 pages, 19 figures, IJCNC, http://airccse.org/journal/cnc/0711cnc13.pdf

Operators of networks covering large areas are confronted with demands from some of their customers who are virtual service providers. These providers may call for the connectivity service which fulfils the specificity of their services, for instance a multicast transition with allocated bandwidth. On the other hand, network operators want to make profit by trading the connectivity service of requested quality to their customers and to limit their infrastructure investments (or do not invest anything at all). We focus on circuit switching optical networks and work on repetitive multicast demands whose source and destinations are {\em \`a priori} known by an operator. He may therefore have corresponding trees "ready to be allocated" and adapt his network infrastructure according to these recurrent transmissions. This adjustment consists in setting available branching routers in the selected nodes of a predefined tree. The branching nodes are opto-electronic nodes which are able to duplicate data and retransmit it in several directions. These nodes are, however, more expensive and more energy consuming than transparent ones. In this paper we are interested in the choice of nodes of a multicast tree where the limited number of branching routers should be located in order to minimize the amount of required bandwidth. After formally stating the problem we solve it by proposing a polynomial algorithm whose optimality we prove. We perform exhaustive computations to show an operator gain obtained by using our algorithm. These computations are made for different methods of the multicast tree construction. We conclude by giving dimensioning guidelines and outline our further work., Comment: 16 pages, 13 figures, extended version from Conference ISCIS 2011

In wireless access network optimization, today's main challenges reside in traffic offload and in the improvement of both capacity and coverage networks. The operators are interested in solving their localized coverage and capacity problems in areas where the macro network signal is not able to serve the demand for mobile data. Thus, the major issue for operators is to find the best solution at reasonable expanses. The femto cell seems to be the answer to this problematic. In this work (This work is supported by the COMET project AWARE. http://www.ftw.at/news/project-start-for-aware-ftw), we focus on the problem of sharing femto access between a same mobile operator's customers. This problem can be modeled as a game where service requesters customers (SRCs) and service providers customers (SPCs) are the players. This work addresses the sharing femto access problem considering only one SPC using game theory tools. We consider that SRCs are static and have some similar and regular connection behavior. We also note that the SPC and each SRC have a software embedded respectively on its femto access, user equipment (UE). After each connection requested by a SRC, its software will learn the strategy increasing its gain knowing that no information about the other SRCs strategies is given. The following article presents a distributed learning algorithm with incomplete information running in SRCs software. We will then answer the following questions for a game with $N$ SRCs and one SPC: how many connections are necessary for each SRC in order to learn the strategy maximizing its gain? Does this algorithm converge to a stable state? If yes, does this state a Nash Equilibrium and is there any way to optimize the learning process duration time triggered by SRCs software?, Comment: 15 pages, 9 figures; extended version from Conference ISCIS 2011