Discrete Mathematics, Algorithms and Applications

A Connected Dominating Set (CDS) can be used to construct a virtual backbone for wireless and mobile ad-hoc networks to make the system hierarchical and efficient. A virtual backbone can significantly improve network throughput, optimize broadband utilization, extend network lifetime, and reduce interference as well as packet retransmissions. Calculating a minimum backbone for a network is critical to reduce routing computation and energy consumption. This problem is a well-known NP-hard optimization problem, which has various applications in practice. In this paper, we propose a new problem based on customer fairness, which looks for a minimum CDS in a given communication model with shortest path constraints. It guarantees that any two clients can communicate with each other through this CDS with hop counts the same as the best path from the original graph, which means that routing on such a CDS will not bring additional traffic for every client. We name this problem as shortest path connected dominating set (SPCDS) and prove its NP-hardness by reduction from Hitting Set. Then we propose a centralized greedy algorithm and an efficient distributed approximation algorithm with approximation ratio Δ to solve SPCDS, where Δ is the maximum vertex degree in the given topology. We also analyze the time complexity, message complexity, and evaluate the efficiency of our distributed heuristic by several numerical experiments and comparisons with previous literatures.

When expressed in terms of base-2 expanions, balanced words are majorized by other words of the same slope. Consequently they have smaller standard deviation and larger geometric mean than all words with given arithmetic mean (or slope), they can be expressed as a doubly stochastic average of any such word, and they can be derived from any such word by a finite number of transfers.

A vertex set D of a connected graph G is a (k, r)-connected dominating set ((k, r)-CDS) if every vertex in V(G)\D is at most r-hops away from at least k vertices in D. Finding a minimum (k, r)-CDS has wireless sensor network as its background. In this paper, we give two approximation algorithms to compute a minimum (k, r)-CDS, which improves previous works in regard of performance ratio.

Centralized matching programs have been established in several countries to organize kidney exchanges between incompatible patient-donor pairs. At the heart of these programs are algorithms to solve kidney exchange problems, which can be modelled as cycle packing problems in a directed graph, involving cycles of length 2, 3, or even longer. Usually, the goal is to maximize the number of transplants, but sometimes the total benefit is maximized by considering the differences between suitable kidneys. These problems correspond to computing cycle packings of maximum size or maximum weight in directed graphs. Here we prove the APX-completeness of the problem of finding a maximum size exchange involving only 2-cycles and 3-cycles. We also present an approximation algorithm and an exact algorithm for the problem of finding a maximum weight exchange involving cycles of bounded length. The exact algorithm has been used to provide optimal solutions to real kidney exchange problems arising from the National Matching Scheme for Paired Donation run by NHS Blood and Transplant, and we describe practical experience based on this collaboration.

In this paper we determine completely the spectra of directed pairwise balanced designs with block sizes from any subset of {3, 4, …, 10} which contains 3. Such designs can be used to construct single-deletion/insertion-correcting codes in which the lengths of the codewords may be different.

Given a multigraph G, an edge cover-coloring of G is called an f-edge cover-coloring, if each color appears at each vertex v at least f(v) times. Let be the maximum positive integer k for which an f-edge cover-coloring with k colors of G exists. An f-edge cover-coloring of G is called a super f-edge cover-coloring, if parallel edges receive distinct colors. Let denote the maximum positive integer k for which a super f-edge cover-coloring with k colors of G exists. A sufficient condition for a graph G to have is given.

The Steiner tree problem is a well known network optimization problem which asks for a connected minimum network (called a Steiner minimum tree) spanning a given point set N. In the original Steiner tree problem the given points lie in the Euclidean plane or space, and the problem has many variants in different applications now. Recently a new type of Steiner minimum tree, probability Steiner minimum tree, is introduced by the authors in the study of phylogenies. A Steiner tree is a probability Steiner tree if all points in the tree are probability vectors in a vector space. The points in a Steiner minimum tree (or a probability Steiner tree) that are not in the given point set are called Steiner points (or probability Steiner points respectively). In this paper we investigate the properties of Steiner points and probability Steiner points, and derive the formulae for computing Steiner points and probability Steiner points in ℓ₁- and ℓ₂-metric spaces. Moreover, we show by an example that the length of a probability Steiner tree on 3 points and the probability Steiner point in the tree are smooth functions with respect to p in d-space.

We look at the problem of coloring locally specially constructed spanners of unit disk graphs. First we present a local approximation algorithm for the vertex coloring problem in Unit Disk Graphs (UDGs) which uses at most four times as many colors as an optimal solution requires. Next we look at the colorability of spanners of UDGs. In particular we present a local algorithm for constructing a 4-colorable spanner of a unit disk graph. The output consists of the spanner and the 4-coloring. The computed spanner also has the properties that it is planar, the degree of a vertex in the spanner is at most 5 and the angles between two edges are at least π/3. By enlarging the locality distance (i.e. the size of the neighborhood which a vertex has to explore in order to compute its color) we can ensure the total weight of the spanner to be arbitrarily close to the weight of a minimum spanning tree.

We prove that a local algorithm cannot compute a bipartite spanner of a unit disk graph and therefore our algorithm needs at most one color more than any local algorithm for the task requires. Moreover, we prove that there is no local algorithm for 3-coloring UDGs or spanners of UDGs, even if the 3-colorability of the graph (or the spanner respectively) is guaranteed in advance.