A tree of rings is an undirected graph obtained from a tree by replacing each node of the tree with a cycle (called tree-node-cycle) and then contracting the edges of the tree so that two cycles corresponding to the two end-nodes of any edge have precisely one node in common and no three tree-node-cycles share a same node. (A more general definition may allow them to share the same node.) Given a set of paths on a tree of rings, the path coloring problem is to color these paths with the smallest number of colors so that any two paths sharing an edge are assigned different colors. In

Consider two sets of strings, B (bad genes) and G (good genes), as well as two integers db and dg (db ≤dg). A frequently occurring problem in computational biology (and other fields) is to find a (distinguishing) substring s of length L that distinguishes the bad strings from good strings, i.e., such that for each string si ∈ B there exists a length-L substring ti of si with d (s, ti) ≤db (close to bad strings), and for every substring ui of length L of every string gi ∈ G, d(s, ui)≥dg (far from good strings). We present a polynomial time approximation scheme to settle the problem; i.e., for any constant >0, the algorithm finds a string s of length L such that for every si ∈ B there is a length-L substring ti of si with d(ti, s)≤(1+)db, and for every substring ui of length L of every gi ∈ G, d (ui, s)≥(1−)dg if a solution to the original pair (db≤dg) exists. Since there is a polynomial number of such pairs (db, dg), we can exhaust all the possibilities in polynomial time to find a good approximation required by the corresponding application problems.

Let G be a graph with vertex set V(G) and edge set E(G); and let g and f be two nonnegative integer-valued functions de3ned on V(G) such that g(x)≤(x) for every vertex x of V(G). We use dG(x) to denote the degree of a vertex x of G. A graph G is called a (g; f)-graph if g(x) ≤G(x) ≤(x) for each x ∈ V(G). Then a spanning subgraph F of G is said to be a (g; f)-factor of G if F itself is a (g; f)-graph. A (g; f)-factorizationof G is a partitionof E(G) into edge disjoint (g; f)-factors. Let F={F1; F2; : : : ; Fm} be a factorizationof G and H be a subgraph of G with m edges. If Fi≤i≤m, has exactly one edge in common with H, we say that F is orthogonal to H. Inthis paper it is proved that every (mg + k;mf − k)-graph contains a subgraph R such that R has a (g; f)-factorizationorthogon al to a givensubgraph with k edges, where m and k are positive integers with 1≤k＜m and g(x)≥0. This result has been conjectured by YaninYan(Sci. China Ser. A 41(1) (1998) 48).

We consider the problem of scheduling jobs with release times and non-identical job sizes on a single batching machine; our objective is to minimize makespan. We present an approximation algorithm with worst-case ratio 2+ε, where ε＞0 can be made arbitrarily small

Grillet established conditions on a partially ordered set under which each maximal antichain meets each maximal chain. Chvatal made a conjecture in terms of graphs that strengthens Grillet's theorem. The purpose of this paper is to prove this conjecture.