Wireless random-access networks with bipartite interference graphs

We consider random-access networks where nodes represent servers with a queue and can be either active or inactive. A node deactivates at unit rate, while it activates at a rate that depends on its queue length, provided none of its neighbors is active. We consider arbitrary bipartite graphs in the limit as the initial queue lengths become large and identify the transition time between the two states where one half of the network is active and the other half is inactive. The transition path is decomposed into a succession of transitions on complete bipartite subgraphs. We formulate a randomized greedy algorithm that takes the graph as input and gives as output the set of transition paths the network is most likely to follow. Along each path we determine the mean transition time and its law on the scale of its mean. Depending on the activation rates, we identify three regimes of behavior.     

Transition time asymptotics of queue-based activation protocols in random-access networks

We consider networks where each node represents a server with a queue. An active node deactivates at unit rate. An inactive node activates at a rate that depends on its queue length, provided none of its neighbors is active.For complete bipartite networks, in the limit as the queues become large, we compute the average transition time between the two states where one half of the network is active and the other half is inactive. We show that the law of the transition time divided by its mean exhibits a trichotomy, depending on the activation rate functions.     

Deterministic random walks on the integers

Jim Propp’s P-machine, also known as the ‘rotor router model’, is a simple deterministic process that simulates a random walk on a graph. Instead of distributing chips to randomly chosen neighbors, it serves the neighbors in a fixed order.We investigate how well this process simulates a random walk. For the graph being the infinite path, we show that, independent of the starting configuration, at each time and on each vertex, the number of chips on this vertex deviates from the expected number of chips in the random walk model by at most a constant c₁, which is approximately 2.29. For intervals of length L, this improves to a difference of O(logL), for the L₂ average of a contiguous set of intervals even to . All these bounds are tight.     

Routing optimization in packet switching communication networks

For routing assignments a special model and an optimization algorithm are proposed. The efficiency of the routing assignments is evaluated by the average value of the total cost of delays for all packets in the network. It is the objective function. The main idea is that traffic, which is transmitted from the source node to the destination node, can be split between two or more logical paths. The minimum of the objective function can be found by varying the traffic on every path and simultaneously from all the source nodes to the destination nodes. If this approach is applied, then the objective function is nonseparable and nonlinear. Because its shape is unknown in advance, an adaptive nonlinear optimization algorithm is proposed. For evaluating its efficiency a special set of test functions has been used.     

Broadcasting secure messages via optimal independent spanning trees in folded hypercubes

Fault-tolerant broadcasting and secure message distribution are important issues for network applications. It is a common idea to design multiple spanning trees with a specific property in the underlying graph of a network to serve as a broadcasting scheme or a distribution protocol for receiving high levels of fault-tolerance and security. An n-dimensional folded hypercube, denoted by FQ_n, is a strengthening variation of hypercube by adding additional links between nodes that have the furthest Hamming distance. In, [12], Ho(1990) proposed an algorithm for constructing n+1 edge-disjoint spanning trees each with a height twice the diameter of FQ_n. Yang et al. (2009), [29] recently proved that Ho’s spanning trees are indeed independent, i.e., any two spanning trees have the same root, say r, and for any other node v≠r, the two different paths from v to r, one path in each tree, are internally node-disjoint. In this paper, we provide another construction scheme to produce n+1 independent spanning trees of FQ_n, where the height of each tree is equal to the diameter of FQ_n plus one. As a result, the heights of independent spanning trees constructed in this paper are shown to be optimal.     

Complete solutions to the Oberwolfach problem for an infinite set of orders

Let n3 and let F be a 2-regular graph of order n. The Oberwolfach problem OP(F) asks for a 2-factorisation of K_n if n is odd, or of K_n−I if n is even, in which each 2-factor is isomorphic to F. We show that there is an infinite set of primes congruent to such that OP(F) has a solution for any 2-regular graph F of order . We also show that for each of the infinitely many with prime, OP(F) has a solution for any 2-regular graph F of order n.     

On the hamiltonian path graph of a graph

The hamiltonian path graph H(F) of a graph F is that graph having the same vertex set as F and in which two vertices u and v are adjacent if and only if F contains a hamiltonian u ? v path. First, in response to a conjecture of Chartrand, Kapoor and Nordhaus, a characterization of nonhamiltonian graphs isomorphic to their hamiltonian path graphs is presented. Next, the maximum size of a hamiltonian graph F of given order such that K?_d ? H(F) is determined. Finally, it is shown that if the degree sum of the endvertices of a hamiltonian path in a graph F with at least five vertices is at least |V(F)| + t(t ? 0), then H(F) contains a complete subgraph of order t + 4.     

Sequential definitions of compactness

A subset F of a topological space is sequentially compact if any sequence of points in F has a convergent subsequence whose limit is in F. We say that a subset F of a topological group X is G-sequentially compact if any sequence of points in F has a convergent subsequence such that where G is an additive function from a subgroup of the group of all sequences of points in X. We investigate the impact of changing the definition of convergence of sequences on the structure of sequentially compactness of sets in the sense of G-sequential compactness. Sequential compactness is a special case of this generalization when G=lim.     

Proper cycles of indefinite quadratic forms and their right neighbors

In this paper we consider proper cycles of indefinite integral quadratic forms F = (a, b, c) with discriminant Δ. We prove that the proper cycles of F can be obtained using their consecutive right neighbors R ⁱ(F) for i ⩾ 0. We also derive explicit relations in the cycle and proper cycle of F when the length l of the cycle of F is odd, using the transformations τ(F) = (−a, b, −c) and ϰ(F) = (−c, b, −a).     

Approximate hierarchical facility location and applications to the bounded depth Steiner tree and range assignment problems

The paper concerns a new variant of the hierarchical facility location problem on metric powers (HFL_β[h]), which is a multi-level uncapacitated facility location problem defined as follows. The input consists of a set F of locations that may open a facility, subsets D₁,D₂,…,D_h−1 of locations that may open an intermediate transmission station and a set D_h of locations of clients. Each client in D_h must be serviced by an open transmission station in D_h−1 and every open transmission station in D_l must be serviced by an open transmission station on the next lower level, D_l−1. An open transmission station on the first level, D₁ must be serviced by an open facility. The cost of assigning a station j on level l1 to a station i on level l−1 is c_ij. For iF, the cost of opening a facility at location i is f_i0. It is required to find a feasible assignment that minimizes the total cost. A constant ratio approximation algorithm is established for this problem. This algorithm is then used to develop constant ratio approximation algorithms for the bounded depth Steiner tree problem and the bounded hop strong-connectivity range assignment problem.     

Galois Reconstruction of Finite Quantum Groups

Let be a (small) category and let F:  →  alg_f be a functor, where alg_f is the category of finite-dimensional measured algebras over a field k (or Frobenius algebras). We construct a universal Hopf algebra A_aut(F) such that F factorizes through a functor :  →  coalg_f(A_aut(F)), where coalg_f(A_aut(F)) is the category of finite-dimensional measured A_aut(F)-comodule algebras. This general reconstruction result allows us to recapture a finite-dimensional Hopf algebra A from the category coalg_f(A) and the forgetful functor ω: coalg_f(A) →  alg_f: we have A  A_aut(ω). Our universal construction is also done in a C*-algebra framework, and we get compact quantum groups in the sense of Woronowicz.     

The least element property of center location on tree networks with applications to distance and precedence constrained problems

In the classicalp-center location model on a network there is a set of customers, and the primary objective is to selectp service centers that will minimize the maximum distance of a customer to a closest center. Suppose that thep centers receive their supplies from an existing central depot on the network, e.g. a warehouse. Thus, a secondary objective is to locate the centers that optimize the primary objective as close as possible to the central depot. We consider tree networks and twop-center models. We show that the set of optimal solutions to the primary objective has a semilattice structure with respect to some natural ordering. Using this property we prove that there is ap-center solution to the primary objective that simultaneously minimizes every secondary objective function which is monotone nondecreasing in the distances of thep centers from the existing central depot.Restricting the location models to a rooted path network (real line) we prove that the above results hold for the respective classicalp-median problems as well.     

Extremal fullerene graphs with the maximum Clar number

A fullerene graph is a cubic 3-connected plane graph with (exactly 12) pentagonal faces and hexagonal faces. Let F_n be a fullerene graph with n vertices. A set of mutually disjoint hexagons of F_n is a sextet pattern if F_n has a perfect matching which alternates on and off every hexagon in . The maximum cardinality of sextet patterns of F_n is the Clar number of F_n. It was shown that the Clar number is no more than . Many fullerenes with experimental evidence attain the upper bound, for instance, C₆₀ and C₇₀. In this paper, we characterize extremal fullerene graphs whose Clar numbers equal . By the characterization, we show that there are precisely 18 fullerene graphs with 60 vertices, including C₆₀, achieving the maximum Clar number 8 and we construct all these extremal fullerene graphs.     

Heuristic algorithms for general <Emphasis Type="Italic">k</Emphasis>-level facility location problems

In a general k-level uncapacitated facility location problem (k-GLUFLP), we are given a set of demand points, denoted by D, where clients are located. Facilities have to be located at a given set of potential sites, which is denoted by F in order to serve the clients. Each client needs to be served by a chain of k different facilities. The problem is to determine some sites of F to be set up and to find an assignment of each client to a chain of k facilities so that the sum of the setup costs and the shipping costs is minimized. In this paper, for a fixed k, an approximation algorithm within a factor of 3 of the optimum cost is presented for k-GLUFLP under the assumption that the shipping costs satisfy the properties of metric space. In addition, when no fixed cost is charged for setting up the facilities and k=2, we show that the problem is strong NP-complete and the constant approximation factor is further sharpen to be 3/2 by a simple algorithm. Furthermore, it is shown that this ratio analysis is tight.     

On the list dynamic coloring of graphs

A proper vertex coloring of a graph G is called a dynamic coloring if for every vertex v of degree at least 2, the neighbors of v receive at least two different colors. Assume that is the minimum number k such that for every list assignment of size k to each vertex of G, there is a dynamic coloring of G such that every vertex is colored with a color from its list. In this paper, it is proved that if G is a graph with no component isomorphic to C₅ and Δ(G)≥3, then , where Δ(G) is the maximum degree of G. This generalizes a result due to Lai, Montgomery and Poon which says that under the same assumptions χ₂(G)≤Δ(G)+1. Among other results, we determine , for every natural number n.     

CONNECTIVITY OF CARTESIAN PRODUCT DIGRAPHS AND FAULT-TOLERANT ROUTINGS OF GENERALIZED HYPERCUBE

ＣＯＮＮＥＣＴＩＶＩＴＹＯＦＣＡＲＴＥＳＩＡＮＰＲＯＤＵＣＴＤＩＧＲＡＰＨＳＡＮＤＦＡＵＬＴ┐ＴＯＬＥＲＡＮＴＲＯＵＴＩＮＧＳＯＦＧＥＮＥＲＡＬＩＺＥＤＨＹＰＥＲＣＵＢＥＸＵＪＵＮＭＩＮＧＡｂｓｔｒａｃｔ．Ｉｎｔｈｉｓｐａｐｅｒ，ｔｈｅｐｒｏｂｌｅｍ...     

Congruence of symmetric matrices over local rings

Let R be a commutative, local, and principal ideal ring with maximal ideal and residue class field F. Suppose that every element of is square. Then the problem of classifying arbitrary symmetric matrices over R by congruence naturally reduces, and is actually equivalent to, the problem of classifying invertible symmetric matrices over F by congruence.     

On the structures of generating iterated function systems of Cantor sets

A generating IFS of a Cantor set F is an IFS whose attractor is F. For a given Cantor set such as the middle-3rd Cantor set we consider the set of its generating IFSs. We examine the existence of a minimal generating IFS, i.e. every other generating IFS of F is an iterating of that IFS. We also study the structures of the semi-group of homogeneous generating IFSs of a Cantor set F in under the open set condition (OSC). If dim_HF<1 we prove that all generating IFSs of the set must have logarithmically commensurable contraction factors. From this Logarithmic Commensurability Theorem we derive a structure theorem for the semi-group of generating IFSs of F under the OSC. We also examine the impact of geometry on the structures of the semi-groups. Several examples will be given to illustrate the difficulty of the problem we study.     

A comparative simulation study on the IFS distribution function estimator

In this paper, we do a comparative simulation study of the standard empirical distribution function estimator versus a new class of nonparametric estimators of a distribution function F, called the iterated function system (IFS) estimator. The target distribution function F is supposed to have compact support. The IFS estimator of a distribution function F is considered as the fixed point of a contractive operator T defined in terms of a vector of parameters p and a family of affine maps which can be both dependent on the sample (X₁,X₂,…,X_n). Given , the problem consists in finding a vector p such that the fixed point of T is “sufficiently near” to F. It turns out that this is a quadratic constrained optimization problem that we propose to solve by penalization techniques. Analytical results prove that IFS estimators for F are asymptotically equivalent to the empirical distribution function (EDF) estimator. We will study the relative efficiency of the IFS estimators with respect to the empirical distribution function for small samples via the Monte Carlo approach.For well-behaved distribution functions F and for a particular family of the so-called wavelet maps the IFS estimators can be dramatically better than the empirical distribution function in the presence of missing data, i.e. when it is only possible to observe data on subsets of the whole support of F.