Mutually independent hamiltonian cycles for the pancake graphs and the star graphs

A hamiltonian cycle C of a graph G is an ordered set u₁,u₂,…,u_n(G),u₁ of vertices such that u_i≠u_j for i≠j and u_i is adjacent to u_i+1 for every i{1,2,…,n(G)−1} and u_n(G) is adjacent to u₁, where n(G) is the order of G. The vertex u₁ is the starting vertex and u_i is the ith vertex of C. Two hamiltonian cycles C₁=u₁,u₂,…,u_n(G),u₁ and C₂=v₁,v₂,…,v_n(G),v₁ of G are independent if u₁=v₁ and u_i≠v_i for every i{2,3,…,n(G)}. A set of hamiltonian cycles {C₁,C₂,…,C_k} of G is mutually independent if its elements are pairwise independent. The mutually independent hamiltonicity IHC(G) of a graph G is the maximum integer k such that for any vertex u of G there exist k mutually independent hamiltonian cycles of G starting at u.In this paper, the mutually independent hamiltonicity is considered for two families of Cayley graphs, the n-dimensional pancake graphs P_n and the n-dimensional star graphs S_n. It is proven that IHC(P₃)=1, IHC(P_n)=n−1 if n≥4, IHC(S_n)=n−2 if n{3,4} and IHC(S_n)=n−1 if n≥5.     

Viral conductance: Quantifying the robustness of networks with respect to spread of epidemics

In this paper, we propose a novel measure, viral conductance (VC), to assess the robustness of complex networks with respect to the spread of SIS epidemics. In contrast to classical measures that assess the robustness of networks based on the epidemic threshold above which an epidemic takes place, the new measure incorporates the fraction of infected nodes at steady state for all possible effective infection strengths. Through examples, we show that VC provides more insight about the robustness of networks than does the epidemic threshold. We also address the paradoxical robustness of Barabási–Albert preferential attachment networks. Even though this class of networks is characterized by a vanishing epidemic threshold, the epidemic requires high effective infection strength to cause a major outbreak. On the contrary, in homogeneous networks the effective infection strength does not need to be very much beyond the epidemic threshold to cause a major outbreak. To overcome computational complexities, we propose a heuristic to compute the VC for large networks with high accuracy. Simulations show that the heuristic gives an accurate approximation of the exact value of the VC. Moreover, we derive upper and lower bounds of the new measure. We also apply the new measure to assess the robustness of different types of network structures, i.e. Watts–Strogatz small world, Barabási–Albert, correlated preferential attachment, Internet AS-level, and social networks. The extensive simulations show that in Watts–Strogatz small world networks, the increase in probability of rewiring decreases the robustness of networks. Additionally, VC confirms that the irregularity in node degrees decreases the robustness of the network. Furthermore, the new measure reveals insights about design and mitigation strategies of infrastructure and social networks.     

Optimal seamless self-assembly of files in linear networks

A file F is sited at one end (the root) of a path in some network. Each non-root node in the path is able to cache part or all of F, and each node may also have a client wanting to download F. Links between neighbors on the path have given transmission delays associated with them, but the delay from a node to its own client, if it has one, is zero. In the seamless, self-assembly paradigm all clients issue requests simultaneously at time 0, each starts to receive segments of F immediately, and continues to receive them until F is fully downloaded. The process must be implemented by means of a distributed self-assembly protocol which is unaware of network structure beyond links to immediate neighbors. We exhibit such a protocol, and show how to assign segments of F to the node caches in such a way that, no matter which nodes are chosen as clients, seamless self-assembly is realized and, simultaneously, the total cache size achieves a lower bound determined solely by the link delays. The paper concludes with a brief discussion of the many open problems arising in systems requiring seamless, or nearly seamless, self assembly of files.     

On minimum congestion routing in rearrangeable multihop lightwave networks

In this article we consider the problem of minimizing the congestion in logically rearrangeable multihop lightwave networks. Namely, we consider a network in which each node is equipped with a small number of transmitters and receivers, and tuning a transmitter at nodei and a receiver at nodej to the same wavelength creates a logical link (i, j) through which traffic could be sent. For a given traffic matrix-the matrix of flows between nodes—the objective is to find the best connectivity diagram and the corresponding flow assignment so that the maximal flow on any link is minimized. We develop a tabu search heuristic that yields a suboptimal connectivity diagram and an optimal flow assignment on it. Computational experiments are conducted on some benchmark data sets, on a real-world traffic matrix, and on some randomly generated problems of larger dimension. The results are compared with known results from the literature and with a known greedy approach. The results suggest that a tabu search—based heuristic is a promising approach for handling this NP-hard combinatorial problem. In addition, we discuss the performance of the method in view of different patterns of input data.     

On the Edge-forwarding Indices of Frobenius Graphs

A G-Frobenius graph F, as defined by Fang, Li, and Praeger, is a connected orbital graph of a Frobenius group G = K × H with Frobenius kernel K and Frobenius complement H. F is also shown to be a Cayley graph, F = Cay（K, S） for K and some subset S of the group K. On the other hand, a network N with a routing function R, written as （N, R）, is an undirected graph N together with a routing R which consists of a collection of simple paths connecting every pair of vertices in the graph. The edge-forwarding index π（N） of a network （N, R）, defined by Heydemann, Meyer, and Sotteau, is a parameter to describe tile maximum load of edges of N. In this paper, we study the edge-forwarding indices of Frobenius graphs. In particular, we obtain the edge-forwarding index of a G-Frobenius graph F with rank（G） ≤ 50.     

Algorithms for single-machine scheduling with stochastic outtree precedence relations to minimize expected weighted flow time or maximum expected lateness

Stochastic single-machine scheduling problems with special tree-like GERT precedence constraints and expected weighted flow time or maximum expected lateness as objective functions are considered. To obtain polynomial algorithms for these problems, Smith's ratio rule and Lawler's rule for the deterministic problems 1¦outtree¦w _v C _v and 1¦prec¦f _max , respectively, are generalized.     

Update games and update networks

In this paper we model infinite processes with finite configurations as infinite games over finite graphs. We investigate those games, called update games, in which each configuration occurs an infinite number of times during a two-person play. We also present an efficient polynomial-time algorithm (and partial characterization) for deciding if a graph is an update network.     

An <Emphasis Type="Italic">L</Emphasis><Subscript>\infty</Subscript>/<Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript>-Constrained Quadratic Optimization Problem with Applications to Neural Networks

Pattern formation in associative neural networks is related to a quadratic optimization problem. Biological considerations imply that the functional is constrained in the L _\infty norm and in the L ₁ norm. We consider such optimization problems. We derive the Euler–Lagrange equations, and construct basic properties of the maximizers. We study in some detail the case where the kernel of the quadratic functional is finite-dimensional. In this case the optimization problem can be fully characterized by the geometry of a certain convex and compact finite-dimensional set.     

Finite method for a nonlinear allocation problem

The problem considered is as follows:m resources are to be allocated ton activities, with resourcei contributing linearly to the potential for activityj according to the coefficientE(i,j). The objective is to minimize some nonlinear function of the potentials. If the objective function is sufficiently well behaved, the problem can be solved in finitely many steps using the method described in this paper.The author thanks S. Toi Lawphongpanich for several helpful references and suggestions.     

An L \infty/ L 1-Constrained Quadratic Optimization Problem with Applications to Neural Networks

Pattern formation in associative neural networks is related to a quadratic optimization problem. Biological considerations imply that the functional is constrained in the L_\infty norm and in the L₁ norm. We consider such optimization problems. We derive the Euler–Lagrange equations, and construct basic properties of the maximizers. We study in some detail the case where the kernel of the quadratic functional is finite-dimensional. In this case the optimization problem can be fully characterized by the geometry of a certain convex and compact finite-dimensional set.     

Region-Fault Tolerant Geometric Spanners

We introduce the concept of region-fault tolerant spanners for planar point sets and prove the existence of region-fault tolerant spanners of small size. For a geometric graph on a point set P and a region F, we define to be what remains of after the vertices and edges of intersecting F have been removed. A  -fault tolerant t-spanner is a geometric graph  on P such that for any convex region F, the graph is a t-spanner for , where is the complete geometric graph on P. We prove that any set P of n points admits a -fault tolerant (1+ε)-spanner of size for any constant ε>0; if adding Steiner points is allowed, then the size of the spanner reduces to  , and for several special cases, we show how to obtain region-fault tolerant spanners of size without using Steiner points. We also consider fault-tolerant geodesic t -spanners: this is a variant where, for any disk D, the distance in between any two points u,v∈P∖D is at most t times the geodesic distance between u and v in ℝ²∖D. We prove that for any P, we can add Steiner points to obtain a fault-tolerant geodesic (1+ε)-spanner of size  . M.A. Abam was supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 612.065.307 and by the MADALGO Center for Massive Data Algorithmics, a Center of the Danish National Research Foundation. M. de Berg was supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 639.023.301. M. Farshi was supported by Ministry of Science, Research and Technology of I.R. Iran. NICTA is funded by the Australian Government as represented by the Department of Broadband, Communications and the Digital Economy and the Australian Research Council through the ICT Centre of Excellence program.     

Finding shortest paths in the plane in the presence of barriers to travel (for any lp - norm)

This paper develops an efficient algorithm for the computation of the shortest paths between given sets of points (origins and destinations) in the plane, when these paths are constrained not to cross any of a finite set of polygonal (open or closed) barriers. It is proved that when distances are measured by an 1_p - norm with 1 < p < ∞, these paths are formed by sequences straight line segments whose intermediate (e.g. apart from origin and destination) end points are barrier vertices. Moreover, only segments that locally support the barriers to which their end points belong are elligible for inclusion in a shortest path. The special case of one origin and one destination is considered, as well as the more general case of many origins and destinations. If n is the number of nodes (origins, destinations and barrier vertices), an algorithm is presented that builds that network of all shortest paths in O(n² log n) time. If the total number of edges in this network is e (bounded by n²), the application of Dijkstra's algorithm enables this computation of the shortest paths from any origin to all destinations in O(e log n) time. If the origins, shortest paths from all origins to all destinations can thus be found in O(ne log n) ≤ O(n^{3 log n}) time.It is also shown that optimal solutions when distances are measured according to the rectilinear or max-norm (i.e. l_p-norm with p = 1 or p = ∞) can be deduced from the results of the algorithm.     

The Downs-Thomson Paradox: Existence, Uniqueness and Stability of User Equilibria

Consider a network where two routes are available for users wishing to travel from a source to a destination. On one route (which could be viewed as private transport) service slows as traffic increases. On the other (which could be viewed as public transport) the service frequency increases with demand. The Downs-Thomson paradox occurs when improvements in service produce an overall decline in performance as user equilibria adjust. Using the model proposed by Calvert [10], with a ⋅|M|1 queue corresponding to the private transport route, and a bulk-service infinite server queue modelling the public transport route, we give a complete analysis of this system in the setting of probabilistic routing. We obtain the user equilibria (which are not always unique), and determine their stability.AMS subject classification: 60K30, 90B15, 90B20, 91A10, 91A13This revised version was published online in June 2005 with corrected coverdate     

Gradient-constrained minimum networks. I. Fundamentals

In three-dimensional space an embedded network is called gradient-constrained if the absolute gradient of any differentiable point on the edges in the network is no more than a given value m. A gradient-constrained minimum Steiner tree T is a minimum gradient-constrained network interconnecting a given set of points. In this paper we investigate some of the fundamental properties of these minimum networks. We first introduce a new metric, the gradient metric, which incorporates a new definition of distance for edges with gradient greater than m. We then discuss the variational argument in the gradient metric, and use it to prove that the degree of Steiner points in T is either three or four. If the edges in T are labelled to indicate whether the gradients between their endpoints are greater than, less than, or equal to m, then we show that, up to symmetry, there are only five possible labellings for degree 3 Steiner points in T. Moreover, we prove that all four edges incident with a degree 4 Steiner point in T must have gradient m if m is less than 0.38. Finally, we use the variational argument to locate the Steiner points in T in terms of the positions of the neighbouring vertices.     

Symmetry property of the throughput in closed tandem queueing networks with finite buffers

In this paper we consider closed tandem queueing networks with finite buffers and blocking before service. With this type of blocking, a server is allowed to start processing a job only if there is an empty space in the next buffer. It was recently conjectured that the throughput of such networks is symmetrical with respect to the population of the network. That is, the throughput of the network with population N is the same as that with population C − N, where C is the total number of buffer spaces in the network. The main purpose of this paper is to prove this result in the case where the service time distributions are of phase type (PH-distribution). The proof is based on the comparison of the sample paths of the network with populations N and C − N. Finally, we also show that this symmetry property is related to a reversibility property of this class of networks.     

Towards better multi-class parametric-decomposition approximations for open queueing networks

Methods are developed for approximately characterizing the departure process of each customer class from a multi-class single-server queue with unlimited waiting space and the first-in-first-out service discipline. The model is (GT _i /GI _i )/1 with a non-Poisson renewal arrival process and a non-exponential service-time distribution for each class. The methods provide a basis for improving parametric-decomposition approximations for analyzing non-Markov open queueing networks with multiple classes. For example, parametric-decomposition approximations are used in the Queueing Network Analyzer (QNA). The specific approximations here extend ones developed by Bitran and Tirupati [5]. For example, the effect of class-dependent service times is considered here. With all procedures proposed here, the approximate variability parameter of the departure process of each class is a linear function of the variability parameters of the arrival processes of all the classes served at that queue, thus ensuring that the final arrival variability parameters in a general open network can be calculated by solving a system of linear equations.     

On DRC‐covering of Kn by cycles

This paper considers the cycle covering of complete graphs motivated by the design of survivable WDM networks, where the requests are routed on INF‐networks which are protected independently from each other. The problem can be stated as follows: for a given graph G, find a cycle covering of the edge set of K_n, where V(K_n) = V(G), such that each cycle in the covering satisfies the disjoint routing constraint (DRC7rpar;, relatively to G, which can be stated as follows: to each edge of K_n we associate in G a path and all the paths associated to the edges of a cycle of the covering must be vertex disjoint. Here we consider the case where G = C_n, a ring of size n and we want to minimize the number of cycles in the covering. We give optimal solutions for the problem as well as for variations of the problem, namely, its directed version and the case when the cycle length is fixed to 4. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 100–112, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10040     

Bottleneck analysis in multiclass closed queueing networks and its application

Asymptotic behavior of queues is studied for large closed multi-class queueing networks consisting of one infinite server station with K classes and M processor sharing (PS) stations. A simple numerical procedure is derived that allows us to identify all bottleneck PS stations. The bottleneck station is defined asymptotically as the station where the number of customers grows proportionally to the total number of customers in the network, as the latter increases simultaneously with service rates at PS stations. For the case when K=M=2, the set of network parameters is identified that corresponds to each of the three possible types of behavior in heavy traffic: both PS stations are bottlenecks, only one PS station is a bottleneck, and a group of two PS stations is a bottleneck while neither PS station forms a bottleneck by itself. In the last case both PS stations are equally loaded by each customer class and their individual queue lengths, normalized by the large parameter, converge to uniformly distributed random variables. These results are directly generalized for arbitrary K=M. Generalizations for K≠M are also indicated. The case of two bottlenecks is illustrated by its application to the problem of dimensioning bandwidth for different data sources in packet-switched communication networks. An engineering rule is provided for determining the link rates such that a service objective on a per-class throughput is satisfied. This revised version was published online in June 2006 with corrections to the Cover Date.     

The probability of connectivity in a hyperbolic model of complex networks

We consider a model for complex networks that was introduced by Krioukov et al. (Phys Rev E 82 (2010) 036106). In this model, N points are chosen randomly inside a disk on the hyperbolic plane according to a distorted version of the uniform distribution and any two of them are joined by an edge if they are within a certain hyperbolic distance. This model exhibits a power‐law degree sequence, small distances and high clustering. The model is controlled by two parameters α and ν where, roughly speaking, α controls the exponent of the power‐law and ν controls the average degree. In this paper we focus on the probability that the graph is connected. We show the following results. For and ν arbitrary, the graph is disconnected with high probability. For and ν arbitrary, the graph is connected with high probability. When and ν is fixed then the probability of being connected tends to a constant that depends only on ν, in a continuous manner. Curiously, for while it is strictly increasing, and in particular bounded away from zero and one, for . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 65–94, 2016     

Connectivity guarantees for wireless networks with directional antennas

We study a combinatorial geometric problem related to the design of wireless networks with directional antennas. Specifically, we are interested in necessary and sufficient conditions on such antennas that enable one to build a connected communication network, and in efficient algorithms for building such networks when possible.We formulate the problem by a set P of n points in the plane, indicating the positions of n transceivers. Each point is equipped with an α-degree directional antenna, and one needs to adjust the antennas (represented as wedges), by specifying their directions, so that the resulting (undirected) communication graph G is connected. (Two points p,q∈P are connected by an edge in G, if and only if q lies in p?s wedge and p lies in q?s wedge.) We prove that if α=60°, then it is always possible to adjust the wedges so that G is connected, and that α?60° is sometimes necessary to achieve this. Our proof is constructive and yields an time algorithm for adjusting the wedges, where k is the size of the convex hull of P.Sometimes it is desirable that the communication graph G contain a Hamiltonian path. By a result of Fekete and Woeginger (1997) [8], if α=90°, then it is always possible to adjust the wedges so that G contains a Hamiltonian path. We give an alternative proof to this, which is interesting, since it produces paths of a different nature than those produced by the construction of Fekete and Woeginger. We also show that for any n and ε>0, there exist sets of points such that G cannot contain a Hamiltonian path if α=90°−ε.