Fast On-Line/Off-Line Algorithms for Optimal Reinforcement of a Network and its Connections with Principal Partition

The problem of computing the strength and performing optimal reinforcement for an edge-weighted graph G(V, E, w) is well-studied. In this paper, we present fast (sequential linear time and parallel logarithmic time) on-line algorithms for optimally reinforcing the graph when the reinforcement material is available continuously on-line. These are the first on-line algorithms for this problem. We invest O(|V|³|E|log|V|) time (equivalent to (|V|) invocations of the fastest known algorithms for optimal reinforcement) in preprocessing the graph before the start of our algorithms. It is shown that the output of our on-line algorithms is as good as that of the off-line algorithms. Thus our algorithms are better than the fastest off-line algorithms in situations when a sequence of more than (|V|) reinforcement problems need to be solved. The key idea is to make use of ideas underlying the theory of Principal Partition of a Graph. Our ideas are easily generalized to the general setting of polymatroid functions. We also present a new efficient algorithm for computation of the Principal Sequence of a graph.     

The Independence Number of Graphs with a Forbidden Cycle and Ramsey Numbers

Let k 5 be a fixed integer and let m = (k – 1)/2. It is shown that the independence number of a C _k-free graph is at least c ₁[ d(v)^{1/(m – 1)}]^{(m – 1)/m} and that, for odd k, the Ramsey number r(C _k, K _n) is at most c ₂(n ^{m + 1}/log n)^1/m , where c ₁ = c ₁(m) > 0 and c ₂ = c ₂(m) > 0.     

The densest <Emphasis Type="Italic">k</Emphasis>-subgraph problem on clique graphs

The Densest k-Subgraph (DkS) problem asks for a k-vertex subgraph of a given graph with the maximum number of edges. The problem is strongly NP-hard, as a generalization of the well known Clique problem and we also know that it does not admit a Polynomial Time Approximation Scheme (PTAS). In this paper we focus on special cases of the problem, with respect to the class of the input graph. Especially, towards the elucidation of the open questions concerning the complexity of the problem for interval graphs as well as its approximability for chordal graphs, we consider graphs having special clique graphs. We present a PTAS for stars of cliques and a dynamic programming algorithm for trees of cliques. M.L. is co-financed within Op. Education by the ESF (European Social Fund) and National Resources. V.Z. is partially supported by the Special Research Grants Account of the University of Athens under Grant 70/4/5821.     

Decomposition of K m,n into 4-cycles and 2t-cycles

In this paper we show the sufficient conditions for the decomposition of the complete bipartite graphs K _2m,2n and K _2n+1,2n+1−F into cycles of two different lengths 4 and 2t, t>2, where F is a 1-factor of K _2n+1,2n+1. After that we prove that the results are true for t=5 and 6. Dedicated to Frank K. Hwang on the occasion of his 65th birthday. An erratum to this article can be found at     

A study on cyclic bandwidth sum

Suppose G is a graph of p vertices. A proper labeling f of G is a one-to-one mapping f:V(G)→{1,2,…,p}. The cyclic bandwidth sum of G with respect to f is defined by CBS _f (G)=∑ _uv∈E(G)|f(v)−f(u)| _p , where |x| _p =min {|x|,p−|x|}. The cyclic bandwidth sum of G is defined by CBS(G)=min {CBS _f (G): f is a proper labeling of G}. The bandwidth sum of G with respect to f is defined by BS _f (G)=∑ _uv∈E(G)|f(v)−f(u)|. The bandwidth sum of G is defined by BS(G)=min {BS _f (G): f is a proper labeling of G}. In this paper, we give a necessary and sufficient condition for BS(G)=CBS(G), and use this to show that BS(T)=CBS(T) when T is a tree. We also find cyclic bandwidth sums of complete bipartite graphs. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. Supported in part by the National Science Council under grants NSC91-2115-M-156-001.     

Distance graphs on R n with 1-norm

Suppose S is a subset of a metric space X with metric d. For each subset D⊆{d(x,y):x,y∈S,x≠y}, the distance graph G(S,D) is the graph with vertex set S and edge set E(S,D)={xy:x,y∈S,d(x,y)∈D}. The current paper studies distance graphs on the n-space R ₁ ⁿ with 1-norm. In particular, most attention is paid to the subset Z ₁ ⁿ of all lattice points of R ₁ ⁿ . The results obtained include the degrees of vertices, components, and chromatic numbers of these graphs. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. Supported in part by the National Science Council under grant NSC-94-2115-M-002-015. Taida Institue for Mathematical Sciences, National Taiwan University, Taipei 10617, Taiwan. National Center for Theoretical Sciences, Taipei Office.     

空气处理过程自动分析软件的开发

介绍一个能对空气处理过程进行自动分析的计算机软件，该软件能生成湿空气的焓－湿图，显示空气处理过程，并对娄在动处理，为空调系统设备选择提供其础数据。     

联图P_(1)(?)T_(n)和P_(1)(?)T_(3)的优美性

本文给出了一类图P_1(?)T_n和P_1(?)T_3,并给出了其优美性的证明.     

多次加入电位滴定法测定铜材中痕量氯

研究了以银电极为指示电极、多次加入格氏电位滴定测定铜材中痕量氯的方法和实验条件，回收率９３．４％，相对标准偏差６．５％．     

Proof of Toft's Conjecture: Every Graph Containing No Fully Odd K4 is 3-Colorable

A fully odd K₄ is a subdivision of K₄ such that each of the six edges of the K₄ is subdivided into a path of odd length. In 1974, Toft conjectured that every graph containing no fully odd K₄ can be vertex-colored with three colors. The purpose of this paper is to prove Toft's conjecture.