已为您找到该学者7条结果 成果回收站
【期刊论文】GENETIC DESIGN OF DRUGS WITHOUT SIDE-EFFECTS∗
李国君, XIAOTIE DENG†, GUOJUN LI‡, ZIMAO LI§, BIN MA¶, AND LUSHENG WANG†
SIAM J. COMPUT. Vol. 32, No.4, pp. 1073-1090,-0001,():
-1年11月30日
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.
approximation algorithms,, computational molecular biology,, distinguishing substring selection
-
67浏览
-
0点赞
-
0收藏
-
0分享
-
55下载
-
0
-
引用
【期刊论文】A 2-approximation algorithm for path coloring on a restricted class of trees of rings
李国君, Xiaotie Deng, a, *, , Guojun Li, b, Wenan Zang, c, and Yi Zhou a
Journal of Algorithms 47(2003)1-13,-0001,():
-1年11月30日
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
this paper,, we present a 2-approximation algorithm for this problem., Path coloring, Trees of rings, Approximation algorithms
-
66浏览
-
0点赞
-
0收藏
-
0分享
-
85下载
-
0
-
引用
李国君, Shuguang Lia, *, Guojun Lib, c, , Xiaoli Wangb, Qiming Liud
Operations Research Letters 33(2005)157-164,-0001,():
-1年11月30日
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
Approximation algorithms, Scheduling, Batch processing, Makespan, Release times
-
51浏览
-
0点赞
-
0收藏
-
0分享
-
83下载
-
0
-
引用
【期刊论文】Orthogonal factorizations of graphs
李国君, GuojunLia, *, Chuanping Chenb, Gang Yuc,
Discrete Mathematics 245(2002)173-194,-0001,():
-1年11月30日
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).
Integer-valued functions, Spanning subgraph, (, g,, f), -factor, Orthogonal factorization
-
51浏览
-
0点赞
-
0收藏
-
0分享
-
34下载
-
0
-
引用
【期刊论文】Proof of Chvátal’s conjecture on maximal stable sets and maximal cliques in graphs
李国君, Xiaotie Deng, a, , Guojun Li, b, c, and Wenan Zangd
Journal of Combinatorial Theory, Series B 91(2004)301-325,-0001,():
-1年11月30日
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.
-
50浏览
-
0点赞
-
0收藏
-
0分享
-
71下载
-
0
-
引用