Discrete Mathematics, Algorithms and Applications

Integrating quadratic form of algebraic connectivity and Perron value of bottleneck matrices, we investigate how the algebraic connectivity of a connected weighted graph behaves under shifting components. Generally speaking, when shift components not containing characteristic vertex from less positive (larger negative) valuation vertices to larger positive (less negative) valuation vertices, or reduce weights of some edges, or add some new blocks, its algebraic connectivity is nonincreasing; when shift components along paths from blocks to other block closer to characteristic block (vertex), or increase weights of some edges, or delete some blocks, its algebraic connectivity is non-decreasing. Therefore, algebraic connectivity could be regarded as a measure of central tendency about blocks of a connected weighted graph with characteristic block (vertex) as its center.

In sensor networks, it is an important task to periodically collect data from an area of interest for time-sensitive applications. The sensed data must be gathered and transmitted to a base station for further processing to meet the end-user queries. Since the network consists of low-cost nodes with limited battery power, it is a challenging task to design an efficient routing scheme that can minimize delay and offer good performance in energy efficiency, and long network lifetimes. In this paper, we propose a distance based multi-clustering in sensor networks using vertex subset degree preserving minimum spanning tree.

Suppose that we are given a set of n elements d of which have a property called defective. A group test can check for any subset, called a pool, whether it contains a defective. It is known that a nearly optimal number of O(d log (n/d)) pools in two stages (where tests within a stage are done in parallel) are sufficient, but then the searcher must know d in advance. Here we explore group testing strategies that use a nearly optimal number of pools and a few stages although d is not known beforehand. We prove a lower bound of Ω(log d/log log d) stages and more general pools versus stages tradeoff. This is almost tight, since O(log d) stages are sufficient for a strategy with O(d log n) pools. As opposed to this negative result, we devise a randomized strategy using O(d log (n/d)) pools in three stages, with any desired success probability 1-ϵ. With some additional measures even two stages are enough. Open questions concern the optimal constant factors and practical implications. A related problem motivated by biological network analysis is to learn hidden vertex covers of a small size k in unknown graphs by edge group tests. (Does a given subset of vertices contain an edge?) We give a one-stage strategy using O(k³log n) pools, with any parameterized algorithm for vertex cover enumeration as a decoder. During the course of this work we also provide a classification of types of randomized search strategies in general.

A mean of a sequence π = (x₁, x₂, …, x_k) of elements of a finite metric space (X, d) is an element x for which is minimum. The function Mean whose domain is the set of all finite sequences on X and is defined by Mean (π) = {x|x is a mean of π} is called the mean function on X. In this note, the mean function on finite trees is characterized axiomatically.

In this paper, we study the sub-coloring and hypo-coloring problems on interval graphs. These problems have applications in job scheduling and distributed computing and can be used as "subroutines" for other combinatorial optimization problems. In the sub-coloring problem, given a graph G, we want to partition the vertices of G into minimum number of sub-color classes, where each sub-color class induces a union of disjoint cliques in G. In the hypo-coloring problem, given a graph G, and integral weights on vertices, we want to find a partition of the vertices of G into sub-color classes such that the sum of the weights of the heaviest cliques in each sub-color class is minimized. We present a "forbidden subgraph" characterization of graphs with sub-chromatic number k and use this to derive a 3-approximation algorithm for sub-coloring interval graphs. For the hypo-coloring problem on interval graphs, we first show that it is NP-complete, and then via reduction to the max-coloring problem, show how to obtain an O(log n)-approximation algorithm for it.

In a convex grid drawing of a plane graph, every edge is drawn as a straight-line segment without any edge-intersection, every vertex is located at a grid point, and every facial cycle is drawn as a convex polygon. A plane graph G has a convex drawing if and only if G is internally triconnected. It has been known that an internally triconnected plane graph G of n vertices has a convex grid drawing on a grid of O(n³) area if the triconnected component decomposition tree of G has at most four leaves. In this paper, we improve the area bound O(n³) to O(n²), which is optimal up to a constant factor. More precisely, we show that G has a convex grid drawing on a 2n × 4n grid. We also present an algorithm to find such a drawing in linear time.

Given are tight upper and lower bounds for the minimum rank among all matrices with a prescribed zero–nonzero pattern. The upper bound is based upon solving for a matrix with a given null space and, with optimal choices, produces the correct minimum rank. It leads to simple, but often accurate, bounds based upon overt statistics of the pattern. The lower bound is also conceptually simple. Often, the lower and an upper bound coincide, but examples are given in which they do not.

Let denote the average Hamming distance of a binary constant weight code C. A_i is the distance distribution of C and B_j is the transform quantity of A_i. Let β(n, M, w) denote the minimum average Hamming distance of a binary constant weight code with length n, size M, and weight w. In this paper, we have established the relation among B_j, and A_i. We also study the problem of determining β(n, M, w) and bounds of β(n, M, w) for different values of M.

Network flows are of growing interest in both applications and theory. Given a network flow with costs and arc capacities, the classical max flow-min cost problem is to send a given amount of flow from the source vertex to the sink vertex at least cost. Among the predominant issues in this field are problems that result when the flow is going through one arc to another arc in the same direction, such as the role of compressors in gas pipeline networks or the role of transformers in electricity wide networks. Hence, in order to minimize the cost of these elements in the network, we perform applications of line-digraphs in the form of an optimization algorithm. This paper proposes a new variant of the max flow-min cost problem. Our objective is to find the smoothest max flow over a given network.

We study a weighted improper coloring problem motivated by a frequency allocation problem. It consists of associating to each vertex a set of p(v) (weight) distinct colors (frequencies), such that the set of vertices having a given color induces a graph of degree at most k (the case k = 0 corresponds to proper coloring). The objective is to minimize the number of colors. We propose approximation algorithms to compute such a coloring for general graphs. We apply these to obtain good approximation ratio for grid and hexagonal graphs. Furthermore we give exact results for the 2-dimensional grid and the triangular lattice when the weights are all the same.

Let D = (d₁, d₂, …, d_n) be a graphic sequence with 0 ≤ d₁ ≤ d₂ ≤ ⋯ ≤ d_n. Any simple graph G with D its degree sequence is called a realization of D. Let R[D] denote the set of all realizations of D. We say that D is H-free if no graph in R[D] contains H as an induced subgraph. In this paper, we prove that Hadwiger's Conjecture is true for graphs whose degree sequences are claw-free or -free.

We study the problem of online scheduling parallel jobs with bounded processing times on 2 machines, and the objective is to minimize makespan. A parallel job requires simultaneous processing on a pre-specified, job-dependent number of machines. The problem is online in the sense that jobs are presented one by one. Once a job is presented, we must irrevocably assign it to some time slot before the next one shows up. We investigate the case where the processing times of jobs are bounded within interval [a, αa] where a > 0 and α > 1. We first prove a lower bound of competitive ratios for online algorithms equal when α ≥ 2 and when 1 < α < 2, respectively. We further prove that the Greedy algorithm proposed in Chan et al. (2008) is -competitive in the case but it cannot be better than -competitive. The results imply that when 1 < α < 2 Greedy has a competitive ratio better than 2, which is the competitive ratio of Greedy in the case without processing time bound.

The group coloring of graphs is a new kind of graph coloring, introduced by Jaeger et al. in 1992, and the group chromatic number of a graph G is denoted by χ_g (G). In this note, we prove that for a positive integer k, a graph G with χ_g (G)>k can be obtained from any complete bipartite graph G₀ with χ_g(G₀)>k by certain types of graph operations.