Diameters of random circulant graphs

The diameter of a graph measures the maximal distance between any pair of vertices. The diameters of many small-world networks, as well as a variety of other random graph models, grow logarithmically in the number of nodes. In contrast, the worst connected networks are cycles whose diameters increase linearly in the number of nodes. In the present study we consider an intermediate class of examples: Cayley graphs of cyclic groups, also known as circulant graphs or multi-loop networks. We show that the diameter of a random circulant 2k-regular graph with n vertices scales as n ^1/k , and establish a limit theorem for the distribution of their diameters. We obtain analogous results for the distribution of the average distance and higher moments.     

Path problems in generalized stars, complete graphs, and brick wall graphs

Path problems such as the maximum edge-disjoint paths problem, the path coloring problem, and the maximum path coloring problem are relevant for resource allocation in communication networks, in particular all-optical networks. In this paper, it is shown that maximum path coloring can be solved optimally in polynomial time for bidirected generalized stars, even in the weighted case. Furthermore, the maximum edge-disjoint paths problem is proved NP-hard for complete graphs (undirected or bidirected), a constant-factor off-line approximation algorithm is presented for the weighted case, and an on-line algorithm with constant competitive ratio is given for the unweighted case. Finally, an open problem concerning the existence of routings that simultaneously minimize the maximum load and the number of colors is solved: an example for a graph and a set of requests is given such that any routing that minimizes the maximum load requires strictly more colors for path coloring than a routing that minimizes the number of colors.     

On randomized broadcasting in Star graphs

One of the most frequently studied problems in the context of information dissemination in communication networks is the broadcasting problem. In this paper, we study the following robust, simple, and scalable randomized broadcasting protocol: at some time t an information is placed at one of the nodes of a graph G, and in the succeeding steps, each informed node chooses one of its neighbours in G uniformly at random, and sends the information to this neighbour.We show that this algorithm spreads an information to all nodes in a Star graph S_n of dimension n within O(logN) steps, with high probability, where N denotes the number of nodes in S_n. To obtain this result, we first establish lower bounds on the edge expansion of small subsets of nodes. Then we introduce a simple but powerful technique for estimating the runtime of randomized broadcasting by analyzing the protocol described above in the reverse order. Using this technique we can also simplify the analysis of this algorithm in Hypercubes [U. Feige, D. Peleg, P. Raghavan, E. Upfal, Randomized broadcast in networks, Random Structures and Algorithms 1 (4) (1990) 447-460].     

A single-copy minimal-time simulation of a torus of automata by a ring of automata

We consider cellular automata on Cayley graphs and we simulate the behavior of a torus of n×m automata (nodes) by a ring of n·m automata (cells). Our simulation technique requires the neighborhood of the nodes to be preserved. We achieve this constraint by copying the contents of nodes on the cells. We consider the problem of minimizing the number of the copies. We prove that it is possible to simulate the behavior of a torus on a ring with a single copy on each cell if and only if n and m satisfy a given condition. In that case we propose a time-optimal algorithm. We thus improve a previous work done by Martin where two copies were requested. When the condition on n and m is not fulfilled one can use the previous algorithm.     

A tight bound on the number of mobile servers to guarantee transferability among dominating configurations

In this paper, we propose a new framework to provide continuous services to users by a collection of mobile servers distributed over an interconnection network. We model those mobile servers as a subset of nodes, and assume that a user can receive the service if at least one adjacent node (including itself) plays the role of a server; i.e., we assume that the service could not be routed via the interconnection network. The main results obtained in this paper are summarized as follows: For the class of trees consisting of n nodes, ⌊n/2⌋ mobile servers are sometimes necessary and always sufficient to realize continuous services by the mobile servers, and for the class of Hamiltonian graphs with n nodes, ⌈(n+1)/3⌉ mobile servers are sometimes necessary and always sufficient.     

Reconstructing edge-disjoint paths

For an undirected graph G=(V,E), the edge connectivity values between every pair of nodes of G can be succinctly recorded in a flow-equivalent tree that contains the edge connectivity value for a linear number of pairs of nodes. We generalize this result to show how we can efficiently recover a maximum set of disjoint paths between any pair of nodes of G by storing such sets for a linear number of pairs of nodes. At the heart of our result is an observation that combining two flow solutions of the same value, one between nodes s and r and the second between nodes r and t, into a feasible flow solution of value f between nodes s and t, is equivalent to solving a stable matching problem on a bipartite multigraph.Our observation, combined with an observation of Chazelle, leads to a data structure, which takes O(n^3.5) time to generate, that can construct the maximum number λ(u,v) of edge-disjoint paths between any pair (u,v) of nodes in time O(α(n,n)λ(u,v)n) time.     

Independent permutations,as related to a problem of Moser and a theorem of Pólya

We introduce the notion of a set of independent permutations on the domain {0, 1,… n ? 1}, and obtain bounds on the size of the largest such set. The results are applied to a problem proposed by Moser in which he asked for the largest number of nodes in a d-cube of side n such that no n of these nodes are collinear. Independent permutations are also related to the problem of placing n non-capturing superqueens (chess queens with wrap-around capability) on an n × n board. As a special case of this treatment we obtain Pólya's theorem that this problem can be solved if and only if n is not a multiple of 2 or 3.     

Toward optimal gossiping schemes with conference calls

n people have distinct bits of information which they can communicate by k-person conference calls. The object of gossip is to inform everyone of everyone else's information. Which networks admit a minimum call gossip scheme? For k = 2 a necessary and sufficient condition for such a network is that it is connected and contains a cycle of length 4. We address the same question for k>2. The values of n are partitioned into 2 classes: trivial and nontrivial. A necessary and sufficient condition is given for networks of size n for trivial n. For nontrivial n a sufficient condition is given and its necessity is conjectured.     

The construction of infinite families of any κ-tight optimal and singular κ-tight optimal directed double loop networks

The double loop network (DLN) is a circulant digraph with n nodes and outdegree 2. It is an important topological structure of computer interconnection networks and has been widely used in the designing of local area networks and distributed systems. Given the number n of nodes, how to construct a DLN which has minimum diameter? This problem has attracted great attention. A related and longtime unsolved problem is for any given non-negative integer k, is there an infinite family of k-tight optimal DLN? In this paper, two main results are obtained (1) for any k ≥ 0, the infinite families of k-tight optimal DLN can be constructed, where the number n(k,e,c) of their nodes is a polynomial of degree 2 in e with integral coefficients containing a parameter c. (2) for any k ≥ 0,an infinite family of singular k-tight optimal DLN can be constructed.     

Isodistant points in competitive network facility location

An isodistant point is any point on a network which is located at a predetermined distance from some node. For some competitive facility location problems on a network, it is verified that optimal (or near-optimal) locations are found in the set of nodes and isodistant points (or points in the vicinity of isodistant points). While the nodes are known, the isodistant points have to be determined for each problem. Surprisingly, no algorithm has been proposed to generate the isodistant points on a network. In this paper, we present a variety of such problems and propose an algorithm to find all isodistant points for given threshold distances associated with the nodes. The number of isodistant points is upper bounded by nm, where n and m are the number of nodes and the number of edges, respectively. Computational experiments are presented which show that isodistant points can be generated in short run time and the number of such points is much smaller than nm. Thus, for networks of moderate size, it is possible to find optimal (or near-optimal) solutions through the Integer Linear Programming formulations corresponding to the discrete version of such problems, in which a finite set of points are taken as location candidates.     

Percolation of interdependent network of networks

Complex networks appear in almost every aspect of science and technology. Previous work in network theory has focused primarily on analyzing single networks that do not interact with other networks, despite the fact that many real-world networks interact with and depend on each other. Very recently an analytical framework for studying the percolation properties of interacting networks has been introduced. Here we review the analytical framework and the results for percolation laws for a Network Of Networks (NONs) formed by n interdependent random networks. The percolation properties of a network of networks differ greatly from those of single isolated networks. In particular, because the constituent networks of a NON are connected by node dependencies, a NON is subject to cascading failure. When there is strong interdependent coupling between networks, the percolation transition is discontinuous (first-order) phase transition, unlike the well-known continuous second-order transition in single isolated networks. Moreover, although networks with broader degree distributions, e.g., scale-free networks, are more robust when analyzed as single networks, they become more vulnerable in a NON. We also review the effect of space embedding on network vulnerability. It is shown that for spatially embedded networks any finite fraction of dependency nodes will lead to abrupt transition.     

A note on a mixed routing and scheduling problem on a grid graph

We consider a particular case of the Fleet Quickest Routing Problem (FQRP) on a grid graph of m × n nodes that are placed in m levels and n columns. Starting nodes are placed at the first (bottom) level, and nodes of arrival are placed at the mth level. A feasible solution of FQRP consists in n Manhattan paths, one for each vehicle, such that capacity constraints are respected. We establish m*, i.e. the number of levels that ensures the existence of a solution to FQRP in any possible permutation of n destinations. In particular, m* is the minimum number of levels sufficient to solve any instance of FQRP involving n vehicles, when they move in the ways that the literature has until now assumed. Existing algorithms give solutions that require, for some values of n, more levels than m*. For this reason, we provide algorithm CaR, which gives a solution in a graph m* × n, as a minor contribution.     

Sorting with networks of data structures

We consider the problem of sorting a permutation using a network of data structures as introduced by Knuth and Tarjan. In general the model as considered previously was restricted to networks that are directed acyclic graphs (DAGs) of stacks and/or queues. In this paper we study the question of which are the smallest general graphs that can sort an arbitrary permutation and what is their efficiency. We show that certain two-node graphs can sort in time Θ(n²) and no simpler graph can sort all permutations. We then show that certain three-node graphs sort in time Ω(n^3/2), and that there exist graphs of k nodes which can sort in time Θ(nlog_kn), which is optimal.     

On the second point-to-point undirected shortest simple path problem

We address the determination of the second point-to-point shortest simple path in undirected networks. The effective reduced cost concept is introduced to compute the second best solution. This concept is used to prove that a path tree containing the second point-to-point shortest simple path is adjacent to any shortest path tree. Therefore, this result immediately implies a method requiring O(m) time once that the shortest path tree is obtained on an undirected network with n nodes and m edges.     

Designing WDM Optical Networks Using Branch-and-Price

In this paper, we present an exact solution procedure for the design of two-layer wavelength division multiplexing (WDM) optical networks with wavelength changers and bifurcated flows. This design problem closely resembles the traditional multicommodity flow problem, except that in the case of WDM optical networks, we are concerned with the routing of multiple commodities in two network layers. Consequently, the corresponding optimization models have to deal with two types of multicommodity variables defined for each of the network layers. The proposed procedure represents one of the first branch-and-price algorithms for a general WDM optical network setting with no assumptions on the number of logical links that can be established between nodes in the network. We apply our procedure in a computational study with four different network configurations. Our results show that for the three tested network configurations our branch-and-price algorithm provides solutions that are on average less than 5 % from optimality. We also provide a comparison of our branch-and-price algorithm with two simple variants of the upper bounding heuristic procedure HLDA that is commonly used for WDM optical network design.     

Agent-based randomized broadcasting in large networks

Mobile agents are software abstractions that can migrate across the links of a network. They naturally extend the object oriented program style and nicely correspond to agents as examined in game theory. In this paper, we introduce a simple, robust, and efficient randomized broadcast protocol within this mobile agent programming paradigm. We show that by using this scheme, broadcasting enquiries in a random graph of certain density O(lnn) steps, where n denotes the number of nodes in the graph. Then, we consider bounded degree graphs and prove that we are able to distribute an information among all nodes in O(D) steps, where D denotes the diameter of the graph. We also show that, in contrast to traditional randomized broadcasting (TRB), graphs exist in which agent-based randomized broadcasting requires Ω(n²) steps. On the other hand, some graphs which require Ω(nlnn) steps to spread the information in the traditional broadcast model, allow very fast agent-based broadcasting. It should be noted that the previously mentioned results are guaranteed with probability 1-o(1/n).     

Formulations and Benders decomposition algorithms for multidepot salesmen problems with load balancing

This paper describes new models and exact solution algorithms for the fixed destination multidepot salesmen problem defined on a graph with n nodes where the number of nodes each salesman is to visit is restricted to be in a predefined range. Such problems arise when the time to visit a node takes considerably longer as compared to the time of travel between nodes, in which case the number of nodes visited in a salesman’s tour is the determinant of their ‘load’. The new models are novel multicommodity flow formulations with O(n²) binary variables, which is contrary to the existing formulations for the same (and similar) problems that typically include O(n³) binary variables. The paper also describes Benders decomposition algorithms based on the new formulations for solving the problem exactly. Results of the computational experiments on instances derived from TSPLIB show that some of the proposed algorithms perform remarkably well in cases where formulations solved by a state-of-the-art optimization code fail to yield optimal solutions within reasonable computation time.     

On the representability of totally unimodular matrices on bidirected graphs

We present a polynomial time algorithm to construct a bidirected graph for any totally unimodular matrix B by finding node-edge incidence matrices Q and S such that QB=S. Seymour’s famous decomposition theorem for regular matroids states that any totally unimodular (TU) matrix can be constructed through a series of composition operations called k-sums starting from network matrices and their transposes and two compact representation matrices B₁,B₂ of a certain ten element matroid. Given that B₁,B₂ are binet matrices we examine the k-sums of network and binet matrices. It is shown that thek-sum of a network and a binet matrix is a binet matrix, but binet matrices are not closed under this operation for k=2,3. A new class of matrices is introduced, the so-called tour matrices, which generalise network, binet and totally unimodular matrices. For any such matrix there exists a bidirected graph such that the columns represent a collection of closed tours in the graph. It is shown that tour matrices are closed under k-sums, as well as under pivoting and other elementary operations on their rows and columns. Given the constructive proofs of the above results regarding the k-sum operation and existing recognition algorithms for network and binet matrices, an algorithm is presented which constructs a bidirected graph for any TU matrix.     

Cycle embedding in star graphs with more conditional faulty edges

The star graph is one of the most attractive interconnection networks. The cycle embedding problem is widely discussed in many networks, and edge fault tolerance is an important issue for networks since edge failures may occur when a network is put into use. In this paper, we investigate the cycle embedding problem in star graphs with conditional faulty edges. We show that there exist fault-free cycles of all even lengths from 6 to n! in any n-dimensional star graph S_n (n ? 4) with ?3n − 10 faulty edges in which each node is incident with at least two fault-free edges. Our result not only improves the previously best known result where the number of tolerable faulty edges is up to 2n − 7, but also extends the result that there exists a fault-free Hamiltonian cycle under the same condition.