International audience

We consider a community formation problem in social networks, where the users are either friends or enemies. The users are partitioned into conflict-free groups (i.e., independent sets in the conflict graph G^- =(V,E) that represents the enmities between users). The dynamics goes on as long as there exists any set of at most k users, k being any fixed parameter, that can change their current groups in the partition simultaneously, in such a way that they all strictly increase their utilities (number of friends i.e., the cardinality of their respective groups minus one). Previously, the best-known upper-bounds on the maximum time of convergence were O(|V|alpha(G^-)) for k <= 2 and O(|V|^3) for k=3, with alpha(G^-) being the independence number of G^-. Our first contribution in this paper consists in reinterpreting the initial problem as the study of a dominance ordering over the vectors of integer partitions. With this approach, we obtain for k <= 2 the tight upper-bound O(|V| min {alpha(G^-), sqrt{|V|}}) and, when G^- is the empty graph, the exact value of order ((2|V|)^{3/2})/3. The time of convergence, for any fixed k >= 4, was conjectured to be polynomial [Escoffier et al., 2012][Kleinberg and Ligett, 2013]. In this paper we disprove this. Specifically, we prove that for any k >= 4, the maximum time of convergence is an Omega(|V|^{Theta(log{|V|})}).

Abstract We study the minimization of ADMs (Add‐Drop Multiplexers) in optical WDM bidirectional rings considering symmetric shortest path routing and all‐to‐all unitary requests. We precisely formulate the problem in terms of graph decompositions, and state a general lower bound for all the values of the grooming factorCandN, the size of the ring. We first study exhaustively the casesC= 1,C= 2, andC= 3, providing improved lower bounds, optimal constructions for several infinite families, as well as asymptotically optimal constructions and approximations. We then study the caseC> 3, focusing specifically on the caseC=k(k+ 1)/2 for somek≥ 1. We give optimal decompositions for several congruence classes ofNusing the existence of some combinatorial designs. We conclude with a comparison of the cost functions in unidirectional and bidirectional WDM rings. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 58(1), 20–35 2011

α-acyclicity is an important notion in database theory. The α-arboricity of a hypergraph [Formula: see text] is the minimum number of α-acyclic hypergraphs that partition the edge set of [Formula: see text]. The α-arboricity of the complete 3-uniform hypergraph is determined completely.

No abstract available.

We study grooming for two-period optical networks, a variation of the traffic grooming problem for wavelength division multiplexed (WDM) ring networks introduced by Colbourn, Quattrocchi, and Syrotiuk. In the two-period grooming problem, during the first period of time there is all-to-all uniform traffic among n nodes, each request using $1/C$ of the bandwidth; and during the second period there is all-to-all uniform traffic only among a subset V of v nodes, each request now being allowed to use $1/C'$ of the bandwidth, where $C' < C$. We determine the minimum drop cost (minimum number of add-drop multiplexers (ADMs)) for any $n,v$ and $C=4$ and $C'\in\{1,2,3\}$. To do this, we use tools of graph decompositions. Indeed the two-period grooming problem corresponds to minimizing the total number of vertices in a partition of the edges of the complete graph $K_n$ into subgraphs, where each subgraph has at most C edges and where furthermore it contains at most $C'$ edges of the complete graph on v specified vertices. Subject to the condition that the two-period grooming has the least drop cost, the minimum number of wavelengths required is also determined in each case.

This work focuses on a class of distributed storage systems whose content may evolve over time. Each component or node of the storage system is mobile and the set of all nodes forms a delay tolerant (ad hoc) network (DTN). The goal of the paper is to study efficient ways for distributing evolving files within DTNs and for managing dynamically their content. We specify to dynamic files where not only the latest version is useful but also previous ones; we restrict however to files where a file has no use if another more recent version is available. The DTN is composed of fixed number of nodes including a single source. At some points in time the source makes available a new version of a single file F. We consider both the cases when (a) nodes do not cooperate and (b) nodes cooperate. In case (a) only the source may transmit a copy of F to a node that it meets, while in case (b) any node may transmit a copy of F to a node that it meets. Scenario (a) is studied under the assumption that the source updates F at discrete times t = 0,1,.. .. Within each slot [t,t + 1) there is a fixed probability that a node meets the source. A file management policy is a set of rules specifying when the source transmits a copy of F to a node (say node i) that it meets; this decision only depends on the age of the version of F (if any) that node i is carrying, where the age is k if this version was created k-1 slots ago. We And the optimal static (resp. dynamic) policy which maximizes a general utility function under a constraint on the number of transmissions within a slot. In particular, we show the existence of a threshold dynamic policy. In scenario (b) F is updated at random points in time. Similar to scenerio (a) we assume that each node knows the age of the file it carries (the case where nodes only know the date of creation of a file is studied in (E. Altman et al., 2008)). Under Markovian assumptions regarding nodes mobility and update frequency of F, we study the stability of the system (aging of the nodes) and derive an (approximate) optimal static policy. We then revisit scenario (a) when the source does not know the number of nodes and the probability that the source meets a node in a slot, and we derive a stochastic approximation algorithm which we show to converge to the optimal static policy found in the complete information setting. Numerical results illustrate the respective performance of optimal static and dynamic policies as well as the benefit of node cooperation.

Let P be a family of dipaths. The load of an arc is the number of dipaths containing this arc. Let pi(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. Let G be a DAG (directed acyclic graph). 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). Here we prove that if G is a DAG without internal cycle, then for any family of dipaths P, w(G, P) = pi(G, P). On the opposite we give examples of DAGs with internal cycles such that the ratio between w(G, P) and pi(G, P) cannot be bounded. We also consider an apparently 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 show that if an UPP-DAG has only one internal cycle, then for any family of dipaths w(G, P) = lceilpi(G, P)rceil and we exhibit an UPP-DAG and a family of dipaths reaching the bound. We conjecture that the ratio between w(G, P) and pi(G, P) cannot be bounded.

Abstract We study the problem of designing a survivable WDM network based on covering the communication requests with subnetworks that are protected independently from each other. We consider here the case when the physical network isT(n), a torus of sizenbyn, the subnetworks are cycles and the communication scheme is all‐to‐all or total exchange (where all pairs of vertices communicate). We will represent the communication requests by a logical graph: a complete graph for the scheme of all‐to‐all. This problem can be modeled as follows: find a cycle partition or covering of the request edges ofK , such that for each cycle in the partition, its request edges can be routed in the physical networkT(n) by a set of vertex disjoint paths (equivalently, the routings with the request cycle form an elementary cycle inT(n)). Let the load of an edge of the WDM network be the number of paths associated with the requests using the edge. The cost of the network depends on the total load (the cost of transmission) and the maximum load (the cost of equipment). To minimize these costs, we will search for an optimal (or quasi optimal) routing satisfying the following two conditions: (a) each request edge is routed by a shortest path overT(n), and (b) the load of each physical edge resulting from the routing of all cycles ofSis uniform or quasi uniform. In this article, we find a covering or partition of the request edges ofK into cycles with an associated optimal or quasi optimal routing such that either (1) the number of cycles of the covering is minimum, or (2) the cycles have size 3 or 4. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(3), 217–225 2007

In the broadcasting problem, one node needs to broadcast a message to all other nodes in a network. If nodes can only communicate with one neighbor at a time, broadcasting takes at least $\lceil \log_2 N \rceil$ rounds in a network of N nodes. In the neighborhood broadcasting problem, the node that is broadcasting needs to inform only its neighbors. In a binary hypercube with N nodes, each node has $\log_2 N$ neighbors, so neighborhood broadcasting takes at least $\lceil \log_2 \log_2 (N+1) \rceil$ rounds. In this paper, we present asymptotically optimal neighborhood broadcast protocols for binary hypercubes.

Abstract We consider on‐board networks in satellites interconnecting entering signals (inputs) to amplifiers (outputs). The connections are made via expensive switches, each of which has four available links. The paths connecting inputs to outputs should be link‐disjoint. Some of the input signals, called priorities, must be connected to the amplifiers that provide the best quality of service (that is, to some specific outputs). In practice, amplifiers are prone to fail, and the faults cannot be repaired. Therefore, extra outputs have to be built into the network to ensure that every input can be routed to operational outputs. Given three integers, n, p, and f, we would like to design a low‐cost network (where the network cost is proportional to the total number of switches) such that it is possible to route all n inputs to n operational amplifiers, and to route the p priorities to the p best quality amplifiers for any set of f faulty and p best‐quality amplifiers. Let R(n, p, f) be the minimum number of switches of such a network. We prove here that $R(n,p,f)\leq{{n+f}\over{2}}\lceil\log_2p\rceil+{{5}\over{2}}(n-p)+g(f)$ with g a function depending only on f. We then compute R(n, p, f) exactly for a few small values of p and f. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 47(1), 9–25 2006

SONET/WDM networks using wavelength add-drop multiplexing can be constructed using certain graph decompositions used to form a grooming, consisting of unions of primitive rings. The cost of such a decomposition is the sum, over all graphs in the decomposition, of the number of vertices of nonzero degree in the graph. The existence of such decompositions with minimum cost, when every pair of sites employs no more than $\frac{1}{6}$ of the wavelength capacity, is determined with a finite number of possible exceptions. Indeed, when the number N of sites satisfies $N \equiv 1 \pmod{3}$, the determination is complete, and when $N \equiv 2 \pmod{3}$, the only value left undetermined is N = 17. When $N \equiv 0 \pmod{3}$, a finite number of values of N remain, the largest being N = 2580. The techniques developed rely heavily on tools from combinatorial design theory.

We address the problem of traffic grooming in WDM rings with all-to-all uniform unitary traffic. We want to minimize the total number of SONET add-drop multiplexers (ADMs) required. We show that this problem corresponds to a partition of the edges of the complete graph into subgraphs, where each subgraph has at most C edges (where C is the grooming ratio) and where the total number of vertices has to be minimized. Using tools of graph and design theory, we optimally solve the problem for practical values and infinite congruence classes of values for a given C, and thus improve and unify all the preceding results. We disprove a conjecture of [A.L. Chiu and E.H. Modiano, 2000] saying that the minimum number of ADMs cannot be achieved with the minimum number of wavelengths and also another conjecture of [J.Q. Hu, 2002].

Abstract We consider traffic grooming in WDM unidirectional rings with all‐to‐all uniform unitary traffic. We determine the minimum number of SONET/SDH add–drop multiplexers (ADMs) required when the grooming ratio is 3. In fact, using tools of design theory, we solve the equivalent edge‐partitioning problem: Find a partition of the edges of the complete graph on n vertices (Kn) into subgraphs having at most three edges and in which the total number of vertices has to be minimized. © 2003 Wiley Periodicals, Inc.

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.

This study considers the design of a survivable WDM network based on covering the initial network with sub-networks, which are protected independently from each other.

In this paper we propose a method which enables us to construct almost optimal broadcast schemes on an n-dimensional hypercube in the circuit switched, /spl Delta/-port model. In this model, an initiator must inform all the nodes of the network in a sequence of rounds. During a round, vertices communicate along arc-disjoint dipaths. Our construction is based on particular sequences of nested binary codes having the property that each code can inform the next one in a single round. This last property is insured by a flow technique and results about symmetric flow networks. We apply the method to design new schemes improving and generalizing the previous results. Our schemes are the best possible algebraic schemes, and they are optimal in the case n=2/sup p/-1.

Gossiping is the process of information diffusion in which each node of a network holds a packet that must be communicated to all other nodes in the network. We consider the problem of gossiping in communication networks under the restriction that communicating nodes can exchange up to a fixed number p of packets at each round. In the first part of the paper we study the extremal case p=1 and we exactly determine the optimal number of communication rounds to perform gossiping for several classes of graphs, including Hamiltonian graphs and complete k-ary trees. For arbitrary graphs we give asymptotically matching upper and lower bounds. We also study the case of arbitrary p and we exactly determine the optimal number of communication rounds to perform gossiping under this hypothesis for complete graphs, hypercubes, rings, and paths. Finally, we investigate the problem of determining sparse networks in which gossiping can be performed in the minimum possible number of rounds.

Our aim was to find bus interconnection networks which connect as many processors as possible, for given upper bounds on the number of connections per processor, the number of processors per bus, and the network diameter. Point-to-point networks are a special case of bus networks in which every bus connects only two processors. In this case, de Bruijn and Kautz networks and their generalizations are known to be among the best families of networks with respect to the aforementioned criteria. In this paper, we present the directed de Bruijn bus networks, which connect two or more processors on a bus and contain the point-to-point de Bruijn networks and their generalization as a special case. We study two different schemes of the directed de Bruijn bus networks. We also show that the directed Kautz bus networks can be defined in the same manner. © 1997 John Wiley & Sons, Inc. Networks 30:205–218, 1997

Given a graph G = (V, E), we define e(X), the mean eccentricity of a vertex X, as the average distance from X to all the other vertices of the graph. The computation of this parameter appears to be nontrivial in the case of the de Bruijn networks. In this paper, we consider upper and lower bounds for e(X). For the directed de Bruijn network, we provide tight bounds as well as the extremal vertices which reach these bounds. These bounds are expressed as the diameter minus some constants. In the case of undirected networks, the computation turns out to be more difficult. We provide lower and upper bounds which differ from the diameter by some small constants. We conjecture that the vertices of the form a· · ·a have the largest mean eccentricity. Numerical computations indicate that the conjecture holds for binary de Bruijn networks with diameters up to 18. We also provide a simple recursive scheme for the computation of the asymptotic mean eccentricity of the vertices a· · ·a. Finally, we prove that the asymptotic difference, when the diameter goes to infinity, between the mean eccentricities of an arbitrary vertex and that of a· · ·a is smaller than a small constant tending to zero with the degree. A byproduct of our analysis is that in both directed and undirected de Bruijn networks most of the vertices are at distance near from the diameter and that all of the mean eccentricities (and therefore the average distance) tend to the diameter when the degree goes to infinity. © 1997 John Wiley & Sons, Inc. Networks 30:187–203, 1997

Abstract Broadcasting is an information dissemination problem in which information originating at one node of a communication network (modeled as a graph) must be transmitted to all other nodes as quickly as possible. A broadcast graph is a graph which permits broadcasting from any originator in minimum time. in this paper, we present new methods for constructing sparse broadcast graphs. Our constructions are based on graph compounding operations which are relative to vertex sets with certain properties that depend on the broadcast protocols of the graphs. We show that many previous methods for constructing sparse broadcast graphs are special cases of our methods. We demonstrate our constructions by producing new sparse broadcast graphs and by showing how many previously constructed graphs can be obtained in a systematic way.

Communication schemes based on store and forward routing, in which a processor can communicate simultaneously with all its neighbors (in parallel) are considered. Moreover, the authors assume that sending a message of length L from a node to a neighbor takes time $\beta + L\tau $. The authors give efficient broadcasting and gossiping protocols for the de Bruijn networks. To do this, arc-disjoint spanning trees of small depth rooted at a given vertex in de Bruijn digraphs are constructed.

Broadcasting is an information dissemination process in which a message is to be sent from a single originator to all members of a network by placing calls over the communication lines of the network. Several previous papers have investigated methods to construct sparse graphs (networks) in which this process can be completed in minimum time from any originator. The graphs produced by these methods contain high degree vertices. [Liestman and Peters, SIAM Journal on Discrete Mathematics, 1 (1988), pp. 531–540 ] and [Bermond and Peyrat, Proceedings of the 19th SE Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium, 1988, pp. 283–292] began an investigation of graphs with fixed maximum degree in which broadcasting can be completed in near minimum time. This investigation is continued in this paper by giving lower bounds and constructing bounded degree graphs that allow rapid broadcasting. The constructions use ideas developed by Jerrum and Skyum [IEEE Transactions on Computers, C-33(2), 1984, pp. 190–194], which allow passing from a graph with good average case behaviour to one with good worst case behaviour. In addition, de Bruijn digraphs [de Bruijn, Koninkhjke Nederlandse Akademie Van Wetenschappen, Indagationes Mathematicae, Series A, 49 (1946), pp. 758–764], minimum broadcast graphs, and sparse broadcast graphs [Bermond, Hell, Liestman, and Peters, Discrete Applied Mathematics, to appear] are used. The resulting graphs yield the best broadcasting time known for bounded degree graphs. Also obtained are asymptotic upper and lower bounds for broadcasting time, as the maximum degree increases.

Abstract This article deals with the problem of minimizing the transmission delay in Illiac‐type interconnection networks for parallel or distributed architectures or in local area networks. A double‐loop network (also known as circulant) G(n,h), consists of a loop of n vertices where each vertex i is also joined by chords to the vertices i ± h mod n. An integer n, a hop h, and a network G(n,h) are called optimal if the diameter of G(n,h) is equal to the lower bound k when n ∈ R[k] = {2k2 − 2k + 2, …,2k2 + 2k + 1}. We determine new dense families of values of n that are optimal and such that the computation of the optimal hop is easy. These families cover almost all the elements of R[k] if k or k + 1 is prime and cover 92% of all values of n up to 106.

In this article, it is shown that if G is an induced subgraph of the dth power of a cycle of length n, and G has minimum degree $d + k$, then G has at least $[ (d + k)/2d ]n$ vertices. This answers a problem of Kézdy.