中国科技论文在线

上传时间

2009年03月06日

【期刊论文】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

引用

上传时间

2009年03月06日

【期刊论文】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

53浏览
0点赞
0收藏
0分享
34下载
0

引用

上传时间

2009年03月06日

【期刊论文】Note Minimizing makespan with release times on identical parallel batching machines

李国君， Shuguang Lia， *， Guojun Lib， c，， Shaoqiang Zhangd

Discrete Applied Mathematics 148(2005)127-134，-0001，（）：

-1年11月30日

摘要

We consider the problem of scheduling n jobs on m identical parallel batching machines. Each job is characterized by a release time and a processing time. Each machine can process up to B (B<n) jobs as a batch simultaneously. The processing time of a batch is equal to the largest processing time among all jobs in the batch. The objective is to minimize the maximum completion time (makespan). We present a polynomial time approximation scheme (PTAS) for this problem.

Polynomial time approximation scheme， Identical parallel batching machines， Scheduling， Makespan

45浏览
0点赞
0收藏
0分享
88下载
0

引用

上传时间

2009年03月06日

【期刊论文】Minimizing makespan on a single batching machine with release times andnon-id entical job sizes

李国君， 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