Group testing in graphs

This paper studies the group testing problem in graphs as follows. Given a graph G=(V,E), determine the minimum number t(G) such that t(G) tests are sufficient to identify an unknown edge e with each test specifies a subset X⊆V and answers whether the unknown edge e is in G[X] or not. Damaschke proved that ⌈log ₂ e(G)⌉≤t(G)≤⌈log ₂ e(G)⌉+1 for any graph G, where e(G) is the number of edges of G. While there are infinitely many complete graphs that attain the upper bound, it was conjectured by Chang and Hwang that the lower bound is attained by all bipartite graphs. Later, they proved that the conjecture is true for complete bipartite graphs. Chang and Juan verified the conjecture for bipartite graphs G with e(G)≤2⁴ or for k≥5. This paper proves the conjecture for bipartite graphs G with e(G)≤2⁵ or for k≥6. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. J.S.-t.J. is supported in part by the National Science Council under grant NSC89-2218-E-260-013. G.J.C. is supported in part by the National Science Council under grant NSC93-2213-E002-28. Taida Institute for Mathematical Sciences, National Taiwan University, Taipei 10617, Taiwan. National Center for Theoretical Sciences, Taipei Office.     

Approximation algorithms for connected facility location problems

We study Connected Facility Location problems. We are given a connected graph G=(V,E) with nonnegative edge cost c _e for each edge e∈E, a set of clients D⊆V such that each client j∈D has positive demand d _j and a set of facilities F⊆V each has nonnegative opening cost f _i and capacity to serve all client demands. The objective is to open a subset of facilities, say , to assign each client j∈D to exactly one open facility i(j) and to connect all open facilities by a Steiner tree T such that the cost is minimized for a given input parameter M≥1. We propose a LP-rounding based 8.29 approximation algorithm which improves the previous bound 8.55 (Swamy and Kumar in Algorithmica, 40:245–269, 2004). We also consider the problem when opening cost of all facilities are equal. In this case we give a 7.0 approximation algorithm.     

On the total {k}-domination number of Cartesian products of graphs

Let γ _t ^{k}(G) denote the total {k}-domination number of graph G, and let denote the Cartesian product of graphs G and H. In this paper, we show that for any graphs G and H without isolated vertices, . As a corollary of this result, we have for all graphs G and H without isolated vertices, which is given by Pak Tung Ho (Util. Math., 2008, to appear) and first appeared as a conjecture proposed by Henning and Rall (Graph. Comb. 21:63–69, 2005). The work was supported by NNSF of China (No. 10701068 and No. 10671191).     

Optimal st-orientations for plane triangulations

For plane triangulations, it has been proved that there exists a plane triangulation G with n vertices such that for any st-orientation of G, the length of the longest directed paths of G in the st-orientation is (Zhang and He in Lecture Notes in Computer Science, vol. 3383, pp. 425–430, 2005). In this paper, we prove the bound is optimal by showing that every plane triangulation G with n-vertices admits an st-orientation with the length of its longest directed paths bounded by . In addition, this st-orientation is constructible in linear time. A by-product of this result is that every plane graph G with n vertices admits a visibility representation with height , constructible in linear time, which is also optimal. A preliminary version of this paper was presented at AAIM 2007.     

On minimum <Emphasis Type="Italic">m</Emphasis>-connected <Emphasis Type="Italic">k</Emphasis>-dominating set problem in unit disc graphs

Minimum m-connected k-dominating set problem is as follows: Given a graph G=(V,E) and two natural numbers m and k, find a subset S⊆V of minimal size such that every vertex in V∖S is adjacent to at least k vertices in S and the induced graph of S is m-connected. In this paper we study this problem with unit disc graphs and small m, which is motivated by the design of fault-tolerant virtual backbone for wireless sensor networks. We propose two approximation algorithms with constant performance ratios for m≤2. We also discuss how to design approximation algorithms for the problem with arbitrarily large m. This work was supported in part by the Research Grants Council of Hong Kong under Grant No. CityU 1165/04E, the National Natural Science Foundation of China under Grant No. 70221001, 10531070 and 10771209.     

On a hyperplane arrangement problem and tighter analysis of an error-tolerant pooling design

In this paper, we formulate and investigate the following problem: given integers d,k and r where k>r≥1,d≥2, and a prime power q, arrange d hyperplanes on to maximize the number of r-dimensional subspaces of each of which belongs to at least one of the hyperplanes. The problem is motivated by the need to give tighter bounds for an error-tolerant pooling design based on finite vector spaces. This work is partially supported by NSF CAREER Award CCF-0347565.     

Domination and total domination in complementary prisms

Let G be a graph and be the complement of G. The complementary prism of G is the graph formed from the disjoint union of G and by adding the edges of a perfect matching between the corresponding vertices of G and . For example, if G is a 5-cycle, then is the Petersen graph. In this paper we consider domination and total domination numbers of complementary prisms. For any graph G, and , where γ(G) and γ _t (G) denote the domination and total domination numbers of G, respectively. Among other results, we characterize the graphs G attaining these lower bounds. Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.     

Challenges of Hong Kong toy manufacturers operating plants in the Pearl River Delta

For years, Hong Kong has been the worlds largest toy exporter. However, as the costs of rent and labor have increased drastically over the past years, Hong Kong toy manufacturers have moved their labor-intensive operations to other lower-wage areas. The Pearl River Delta (PRD) region of the Peoples Republic of China (PRC) has been one of their favorite choices for outsourcing because of cheap and available labor. This paper explores, using data culled from interviews with the senior management of five leading Hong Kong toy companies, how some Hong Kong toy manufacturers overcame various strategic management issues after having made the move to the PRD. The results are presented within five major areas of concern: rules and regulations, the less-developed infrastructure, R&D, relationship with suppliers, and new technology, and they are used to show how the manufacturers were able to overcome various strategic constraints in order to accomplish outstanding performance. Supporting data were gathered through factory visits in order to better understand the actual operations within the PRD. This collected experience should be beneficial to other manufacturers interested in operating plants within the PRD.     

Paired-domination in generalized claw-free graphs

In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998) 199–206). A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The paired-domination number of G, denoted by , is the minimum cardinality of a paired-dominating set of G. If G does not contain a graph F as an induced subgraph, then G is said to be F-free. Haynes and Slater (Networks 32 (1998) 199–206) showed that if G is a connected graph of order , then and this bound is sharp for graphs of arbitrarily large order. Every graph is -free for some integer a ≥ 0. We show that for every integer a ≥ 0, if G is a connected -free graph of order n ≥ 2, then with infinitely many extremal graphs.     

An exponential (matching based) neighborhood for the vehicle routing problem

We introduce an exponential neighborhood for the Vehicle Routing Problem (vrp) with unit customers’ demands, and we show that it can be explored efficiently in polynomial time by reducing its exploration to a particular case of the Restricted Complete Matching (rcm) problem that we prove to be polynomial time solvable using flow techniques. Furthermore, we show that in the general case with non-unit customers’ demands the exploration of the neighborhood becomes an -hard problem.     

Lower bounds and a tabu search algorithm for the minimum deficiency problem

An edge coloring of a graph G=(V,E) is a function c:E→ℕ that assigns a color c(e) to each edge e∈E such that c(e)≠c(e′) whenever e and e′ have a common endpoint. Denoting S _v (G,c) the set of colors assigned to the edges incident to a vertex v∈V, and D _v (G,c) the minimum number of integers which must be added to S _v (G,c) to form an interval, the deficiency D(G,c) of an edge coloring c is defined as the sum ∑ _v∈V D _v (G,c), and the span of c is the number of colors used in c. The problem of finding, for a given graph, an edge coloring with a minimum deficiency is NP-hard. We give new lower bounds on the minimum deficiency of an edge coloring and on the span of edge colorings with minimum deficiency. We also propose a tabu search algorithm to solve the minimum deficiency problem and report experiments on various graph instances, some of them having a known optimal deficiency.     

Sublinear time width-bounded separators and their application to the protein side-chain packing problem

Given d>2 and a set of n grid points Q in ℜ ^d , we design a randomized algorithm that finds a w-wide separator, which is determined by a hyper-plane, in sublinear time such that Q has at most points on either side of the hyper-plane, and at most points within distance to the hyper-plane, where c _d is a constant for fixed d. In particular, c ₃=1.209. To our best knowledge, this is the first sublinear time algorithm for finding geometric separators. Our 3D separator is applied to derive an algorithm for the protein side-chain packing problem, which improves and simplifies the previous algorithm of Xu (Research in computational molecular biology, 9th annual international conference, pp. 408–422, 2005). This research is supported by Louisiana Board of Regents fund under contract number LEQSF(2004-07)-RD-A-35. The part of this research was done while Bin Fu was associated with the Department of Computer Science, University of New Orleans, LA 70148, USA and the Research Institute for Children, 200 Henry Clay Avenue, New Orleans, LA 70118, USA.     

Parameterized dominating set problem in chordal graphs: complexity and lower bound

In this paper, we study the parameterized dominating set problem in chordal graphs. The goal of the problem is to determine whether a given chordal graph G=(V,E) contains a dominating set of size k or not, where k is an integer parameter. We show that the problem is W[1]-hard and it cannot be solved in time unless 3SAT can be solved in subexponential time. In addition, we show that the upper bound of this problem can be improved to when the underlying graph G is an interval graph.     

Improved algorithms for largest cardinality 2-interval pattern problem

The 2-INTERVAL PATTERN problem is to find the largest constrained pattern in a set of 2-intervals. The constrained pattern is a subset of the given 2-intervals such that any pair of them are R-comparable, where model . The problem stems from the study of general representation of RNA secondary structures. In this paper, we give three improved algorithms for different models. Firstly, an O(n{log} n +L) algorithm is proposed for the case , where is the total length of all 2-intervals (density d is the maximum number of 2-intervals over any point). This improves previous O(n ²log n) algorithm. Secondly, we use dynamic programming techniques to obtain an O(nlog n + dn) algorithm for the case R = { <, ⊏ }, which improves previous O(n ²) result. Finally, we present another algorithm for the case with disjoint support(interval ground set), which improves previous O(n ²□n) upper bound. A preliminary version of this article appears in Proceedings of the 16th Annual International Symposium on Algorithms and Computation, Springer LNCS, Vol. 3827, pp. 412–421, Hainan, China, December 19–21, 2005.     

Optimal strategies for the one-round discrete Voronoi game on a line

The one-round discrete Voronoi game, with respect to a n-point user set  $\mathcal {U}$ , consists of two players Player 1 (P1) and Player 2 (P2). At first, P1 chooses a set $\mathcal{F}_{1}$ of m facilities following which P2 chooses another set $\mathcal{F}_{2}$ of m facilities, disjoint from  $\mathcal{F}_{1}$ , where m(=O(1)) is a positive constant. The payoff of P2 is defined as the cardinality of the set of points in $\mathcal{U}$ which are closer to a facility in $\mathcal{F}_{2}$ than to every facility in $\mathcal{F}_{1}$ , and the payoff of P1 is the difference between the number of users in $\mathcal{U}$ and the payoff of P2. The objective of both the players in the game is to maximize their respective payoffs. In this paper, we address the case where the points in $\mathcal{U}$ are located along a line. We show that if the sorted order of the points in $\mathcal{U}$ along the line is known, then the optimal strategy of P2, given any placement of facilities by P1, can be computed in O(n) time. We then prove that for m≥2 the optimal strategy of P1 in the one-round discrete Voronoi game, with the users on a line, can be computed in $O(n^{m-\lambda_{m}})$ time, where 0<λ _m <1, is a constant depending only on m.     

Packing cycles exactly in polynomial time

Let G=(V,E) be an undirected graph in which every vertex v∈V is assigned a nonnegative integer w(v). A w-packing is a collection of cycles (repetition allowed) in G such that every v∈V is contained at most w(v) times by the members of . Let 〈w〉=2|V|+∑ _v∈V ⌈log (w(v)+1)⌉ denote the binary encoding length (input size) of the vector (w(v): v∈V) ^T . We present an efficient algorithm which finds in O(|V|⁸〈w〉²+|V|¹⁴) time a w-packing of maximum cardinality in G provided packing and covering cycles in G satisfy the ℤ₊-max-flow min-cut property.     

An Improved Randomized Approximation Algorithm for Max TSP

We present an O(n³)-time randomized approximation algorithm for the maximum traveling salesman problem whose expected approximation ratio is asymptotically , where n is the number of vertices in the input (undirected) graph. This improves the previous best.Part of work done while visiting City University of Hong Kong.     

Integer-magic spectra of sun graphs

Let A be a non-trivial Abelian group. A graph G=(V,E) is A-magic if there exists a labeling f:E→A∖{0} such that the induced vertex set labeling f ⁺:V→A, defined by f ⁺(v)=∑f(uv) where the sum is over all uv∈E, is a constant map. The integer-magic spectrum of a graph G is the set IM(G)={k∈ℕ∣G is ℤ _k -magic}. A sun graph is obtained from an n-cycle, by attaching paths to each pair of adjacent vertices in the cycle. In this paper, we investigate the integer-magic spectra of some sun graphs. Dedicated to Prof. Frank K. Hwang, on the occasion of his 65th birthday. Supported by Faculty Research Grant, Hong Kong Baptist University.     

Objective functions with redundant domains

Let $(E,{ \mathcal{A}})$ be a set system consisting of a finite collection ${ \mathcal{A}}$ of subsets of a ground set E, and suppose that we have a function ? which maps ${ \mathcal{A}}$ into some set S. Now removing a subset K from E gives a restriction ${ \mathcal{A}}(\bar{K})$ to those sets of ${ \mathcal{A}}$ disjoint from K, and we have a corresponding restriction $\phi|_{\hspace {.02in}{ \mathcal{A}}(\bar{K})}$ of our function ?. If the removal of K does not affect the image set of ?, that is $\mbox {Im}(\phi|_{\hspace {.02in}{ \mathcal{A}}(\bar{X})})=\mbox {Im}(\phi)$ , then we will say that K is a kernel set of ${ \mathcal{A}}$ with respect to ?. Such sets are potentially useful in optimisation problems defined in terms of ?. We will call the set of all subsets of E that are kernel sets with respect to ? a kernel system and denote it by $\mathrm {Ker}_{\phi}({ \mathcal{A}})$ . Motivated by the optimisation theme, we ask which kernel systems are matroids. For instance, if ${ \mathcal{A}}$ is the collection of forests in a graph G with coloured edges and ? counts how many edges of each colour occurs in a forest then $\mathrm {Ker}_{\phi}({ \mathcal{A}})$ is isomorphic to the disjoint sum of the cocycle matroids of the differently coloured subgraphs; on the other hand, if ${ \mathcal{A}}$ is the power set of a set of positive integers, and ? is the function which takes the values 1 and 0 on subsets according to whether they are sum-free or not, then we show that $\mathrm {Ker}_{\phi}({ \mathcal{A}})$ is essentially never a matroid.     

Error-correcting pooling designs associated with the dual space of unitary space and ratio efficiency comparison

In this paper, we construct a d ^z -disjunct matrix with subspaces in a dual space of Unitary space , then give its several properties. As the smaller the ratio efficiency is, the better the pooling design is. We compare the ratio efficiency of this construction with others, such as the ratio efficiency of the construction of set, the general space and the dual space of symplectic space. In addition, we find it smaller under some conditions. Supported by NSF of the Education Department of Hebei Province (2007127) and NSF of Hebei Normal University (L2004B04).