完全图全符号控制数的较小上界和下确界

设图G=G(V,E),令函数f∶V∪E→{-1,1},f的权w(f)=∑x∈V∪Ef[x],对V∪E中任一元素,定义f[x]=∑y∈NT[x]f(y),这里NT[x]表示V∪E中x及其关联边、邻点的集合.图G的全符号控制函数为f∶V∪E→{-1,1},满足对所有的x∈V∪E有f[x]1,图G的全符号控制数γT(G)就是图G上全符号控制数的最小权,称其f为图G的γT-函数.本文得到了完全图全符号控制数的一个较小上界和下确界.     

最短路的 Hu 算法的代数证明

设有一个有向图,顶点集合为 V={V_i|i=1,2…n},有向边集合记作 E.对于每一条有向边,对应一个实数,可正、可负、可为零,这个数叫做这条有向边的长度.这样的有向图叫做(一般)网络,记作 N(V,E).     

三路树P(m,n,t)是边幻图的证明(Ⅱ)

令简单图G=(V,E)是有p个顶点q条边的图.假设G的顶点和边由1,2,…,p+q所标号,且f:V ∪E→{1,2,…,p+q}是一个双射,如果对所有的边xy,f(x)+f(y)+f(xy)是常量,则称图G是边幻图(edge-magic).本文证明了三路树P(m,n,t)当n为偶数,t=n+2时也是边幻图.     

三路树P(m,n,t)是边幻图的证明(II)

令简单图G=(V,E)是有p个顶点q条边的图.假设G的顶点和边由1,2,…,p+q所标号,且f:V∪E→{1,2,…,p+q}是一个双射,如果对所有的边xy,f(x)+f(y)+f(xy)是常量,则称图G是边幻图(edge-magic).本文证明了三路树P(m,n,t)当n为偶数,t=n+2时也是边幻图.     

图K_(2n)\E(F_4)(n≥12)的点可区别边染色

对简单图G(V,E),设f是从E(G)到{1,2,…,k}的映射,k为自然数,如果.f满足:1)对任意的uv,uw∈E(G),v≠w,有.f(uv)≠f(uw);2)对任意的u,v∈V(G),u≠v,有C(u)≠C(v).则称f为图G的k-点可区别边染色法,而最小的k被称为点可区别边色数(其中C(u)={f(uv)|uv∈E(G)}.研究了图K_(2n)\E(F_4)(n≥12)的点可区别边色数.     

有向图n·■_m的优美性

给定有向图D(V,E),如果存在一个单射f:V(D)→{0,1,…,|E|}使得对于每条有向边(u,v),诱导函数f′:E(D)→{1,2,…,|E|}是一个双射函数,其中,f′(u,v)=[f(v)-f(u)](mod(|E|+1)),则f称为有向图D(V,E)的优美标号,f′称为有向图D(V,E)的诱导的边的优美标号.本文讨论了有向图n.■m的优美性,并且证明了当m=23且n为偶数时,n.■m是优美有向图.     

图K_(2n)\E(K_(2,m))(n≥9,m≥3)的点可区别边染色

对简单图G(V,E),设f是从E(G)到{1,2,…,κ}的映射,κ为自然数,如果f满足:1)对任意的uv,uw∈E(G),v≠w,有f(uv)≠f(uw);2)对任意的u,v∈V(G),u≠v,有C(u)≠C(v).则称f为图G的κ-点可区别边染色法,而最小的κ被称为点可区别边色数(其中C(u)={f(uv)|uv∈E(G)}).研究了图K_(2n)\E(K_(2,m))(n≥9,m≥3)的点可区别边色数.     

圈的k-距离控制多项式

设图G=(V,E)是n阶简单图,C_n表示具有n个点的圈.给出了圈C_n的k-距离控制多项式的基本性质和递推公式.其次,构造了一个二元函数f(u,v),使得k-距离控制多项式的系数d_k(C_n,i)与f(u,v)展开式中项u~nv~i的系数相等.     

环状硅酸盐图的友好指数集

Let G be a graph with vertex set V(G) and edge set E(G). A labeling f : V(G) →Z2 induces an edge labeling f*: E(G) → Z2 defined by f*(xy) = f(x) + f(y), for each edge xy ∈ E(G). For i ∈ Z2, let vf(i) = |{v ∈ V(G) : f(v) = i}| and ef(i) = |{e ∈ E(G) : f*(e) =i}|. A labeling f of a graph G is said to be friendly if |vf(0)- vf(1)| ≤ 1. The friendly index set of the graph G, denoted FI(G), is defined as {|ef(0)- ef(1)|: the vertex labeling f is friendly}. This is a generalization of graph cordiality. We investigate the friendly index sets of cyclic silicates CS(n, m).     

图 P2×Cn的均匀邻强边色数

对图G(V,E),一正常边染色f若满足(1)对(V)uv∈E(G),f[u]≠f[v],其中f[u]={f(uv)|uv∈E};(2)对任意i≠j,有||E|-|Ej||≤1,其中Ei={e| e∈E(G)且f(e)=i}.则称f为G(V,E)的一k-均匀邻强边染色,简称k-EASC,并且称Xcas(G)=min{k|存在G(V,E)的一k-EASC为G(V,E)的均匀邻强边色数.本文得到了图P2×Cn的均匀邻强边色数.     

Neighborhood-following algorithms for linear programming

In this paper, we present neighborhood-following algorithms for linear programming. When the neighborhood is a wide neighborhood, our algorithms are wide neighborhood primal-dual interior point algorithms. If the neighborhood degenerates into the central path, our algorithms also degenerate into path-following algorithms. We prove that our algorithms maintain the O(n~(1/2)L)-iteration complexity still, while the classical wide neighborhood primal-dual interior point algorithms have only the O(nL)-iteration complexity. We also proved that the algorithms are quadratic convergence if the optimal vertex is nondegenerate. Finally, we show some computational results of our algorithms.     

A hybrid algorithm for finding thekth smallest ofn elements in O(n) time

The problem of finding thekth smallest ofn elements can be solved either with O(n) algorithms or with O(n ²) algorithms. Although they require a higher number of operations in the worst case, O(n ²) algorithms are generally preferred to O(n) algorithms because of their better average performance. We present a hybrid algorithm which is O(n) in the worst case and efficient in the average case.     

On the worst case complexity of potential reduction algorithms for linear programming

There are several classes of interior point algorithms that solve linear programming problems in O(√nL) iterations. Among them, several potential reduction algorithms combine both theoretical (O(√nL) iterations) and practical efficiency as they allow the flexibility of line searches in the potential function, and thus can lead to practical implementations. It is a significant open question whether interior point algorithms can lead to better complexity bounds. In the present paper we give some negative answers to this question for the class of potential reduction algorithms. We show that, even if we allow line searches in the potential function, and even for problems that have network structure, the bound O(√nL) is tight for several potential reduction algorithms, i.e., there is a class of examples with network structure, in which the algorithms need at least Θ(√nL) iterations to find an optimal solution. The research of the author was partially supported by a Presidential Young Investigator Award DDM-9158118 with matching funds from Draper Laboratory.     

Parallel and superfast algorithms for Hankel systems of equations

Summary Utilizing kernel structure properties a unified construction of Hankel matrix inversion algorithms is presented. Three types of algorithms are obtained: 1)O(n ²) complexity Levinson type, 2)O (n) parallel complexity Schur-type, and 3)O(n log² n) complexity asymptotically fast ones. All algorithms work without additional assumption (like strong nonsingularity).     

任意长—维DFT的MIMD并行算法

本文提出了共享与分布式存储计算机上任意长—维ＤＦＴ的ＭＩＭＤ并行算法，若Ｎ＝Ｏ（ｐ，ｑ），则算法需要次算术运算。其中，Ｐ与Ｎ可为任意自然数，分别表示处理机台数与ＤＦＴ长度．本文算法具有很高的并行效率．     

Local search in routing problems with time windows

We develop local search algorithms for routing problems with time windows. The presented algorithms are based on thek-interchange concept. The presence of time windows introduces feasibility constraints, the checking of which normally requires O(N) time. Our method reduces this checking effort to O(1) time. We also consider the problem of finding initial solutions. A complexity result is given and an insertion heuristic is described.     

Fast Algorithms for Centro-Symmetric and Centro-Skewsymmetric Toeplitz-Plus-Hankel Matrices

Subject of the paper are centro-symmetric and centro-skewsymmetric Toeplitz-plus-Hankel matrices with the property that all central submatrices are nonsingular. Fast algorithms are presented that solve an n×n system of equations with O(n ²) operations in sequential and O(n) operations in parallel processing and compute the ZW-factorization with the same computational complexity. These algorithms are more efficient than existing algorithms because they fully exploit the symmetry properties of the matrices.     

Efficient parallel recognition of cographs

In this paper, we establish structural properties for the class of complement reducible graphs or cographs, which enable us to describe efficient parallel algorithms for recognizing cographs and for constructing the cotree of a graph if it is a cograph; if the input graph is not a cograph, both algorithms return an induced P₄. For a graph on n vertices and m edges, both our cograph recognition and cotree construction algorithms run in time and require O((n+m)/logn) processors on the EREW PRAM model of computation. Our algorithms are motivated by the work of Dahlhaus (Discrete Appl. Math. 57 (1995) 29–44) and take advantage of the optimal O(logn)-time computation of the co-connected components of a general graph (Theory Comput. Systems 37 (2004) 527–546) and of an optimal O(logn)-time parallel algorithm for computing the connected components of a cograph, which we present. Our results improve upon the previously known linear-processor parallel algorithms for the problems (Discrete Appl. Math. 57 (1995) 29–44; J. Algorithms 15 (1993) 284–313): we achieve a better time-processor product using a weaker model of computation and we provide a certificate (an induced P₄) whenever our algorithms decide that the input graphs are not cographs.     

ALGORITHMS FOR IMPLEMENTATION OF GENERAL LIMIT REPRESENTATIONS OF GENERALIZED INVERSES

1. Introduction and PreliminariesThe set of all m x n comPlex matrices of rank r is denoted by cy". By I we denote anappropriate ideniity matrix. Also, n(A) denotes the trace of a square matriX A. By n(A) andN(A) are denoted the range and the null space of A, respectively Finally ad(A) and det(A)denote the adoint of the matris A and the determinant of A, respectivelyFOr any matrix A E crxn consider the following equations in X:(1) AXA=A, (2) XAX=X, (3) (AX)*=AX, (4) (XA)*=XAand…