关于乘积图的二维带宽问题

给出一般乘积图的二维带宽的界，并解决一类乘积图的二维带宽问题．最后给出完全ｋ部图的二维带宽。     

Finding minimal spanning trees in a euclidean coordinate space

The minimal spanning tree problem of a point set in ak-dimensional Euclidean space is considered and a new version of the multifragmentMST-algorithm of Bentley and Friedman is given. The minimal spanning tree is found by repeatedly joining the minimal subtree with the closest subtree. Ak-d tree is used for choosing the connecting edges. Computation time of the algorithm depends on the configuration of the point set: for normally distributed random points the algorithm is very fast. Two extreme cases demandingO(n logn) andO(n ²) operations,n being the cardinality of the point set, are also given.     

Recognizing graphs without asteroidal triples

We consider the problem of recognizing AT-free graphs. Although there is a simple O(n³) algorithm, no faster method for solving this problem had been known. Here we give three different algorithms which have a better time complexity for graphs which are sparse or have a sparse complement; in particular we give algorithms which recognize AT-free graphs in , , and O(n^2.82+nm). In addition we give a new characterization of graphs with bounded asteroidal number by the help of the knotting graph, a combinatorial structure which was introduced by Gallai for considering comparability graphs.     

可能行无限图C~*-代数

本文研究可能行无限有向图的C~*-代数。对于一个可能行无限的有向图E,通过引进集合S(μ,v),将行无限点上的算子拓扑强收敛关系代数化表示出来,并由此构造了一个结构丰富的非零*-代数H_E;进而利用H_E证明了一个由Cuntz-Krieger E-族{s_e,p_v}生成的泛C~*-代数 C~*(E)的存在性,并且证明了H_E和 C~*(E)在图同构意义下不依赖于E的选择,从而是可能行无限有向图的同构不变量。     

Feasible Graphs and Colorings

The problem of when a recursive graph has a recursive k-coloring has been extensively studied by Bean, Schmerl, Kierstead, Remmel, and others. In this paper, we study the polynomial time analogue of that problem. We develop a number of negative and positive results about colorings of polynomial time graphs. For example, we show that for any recursive graph G and for any k, there is a polynomial time graph G′ whose vertex set is {0,1}* such that there is an effective degree preserving correspondence between the set of k-colorings of G and the set of k-colorings of G′ and hence there are many examples of k-colorable polynomial time graphs with no recursive k-colorings. Moreover, even though every connected 2-colorable recursive graph is recursively 2-colorable, there are connected 2-colorable polynomial time graphs which have no primitive recursive 2-coloring. We also give some sufficient conditions which will guarantee that a polynomial time graph has a polynomial time or exponential time coloring.     

互补图的星色数

本文给出互补图的星色数所满足的一些必要条件，并确定一些图类的星色数．     

A computational study of graph partitioning

LetG = (N, E) be an edge-weighted undirected graph. The graph partitioning problem is the problem of partitioning the node setN intok disjoint subsets of specified sizes so as to minimize the total weight of the edges connecting nodes in distinct subsets of the partition. We present a numerical study on the use of eigenvalue-based techniques to find upper and lower bounds for this problem. Results for bisecting graphs with up to several thousand nodes are given, and for small graphs some trisection results are presented. We show that the techniques are very robust and consistently produce upper and lower bounds having a relative gap of typically a few percentage points.Corresponding author.     

A simple procedure to compute the nucleolus of Γ-component additive games

Summary This paper considers the Γ-component additive games which take into account the possibilities of communications among agents located in the nodes of a tree graph Γ. Gains from cooperation are derived from agents who are directly connected in the tree. We introduce a new procedure to compute the nucleolus for these games. This procedure is quick and it does not use linear programming techniques. We finally present a numerical example of a sequencing game to illustrate the procedure. This research has been supported partially by UPV-EHU research projects: 035.321-HA 130/93 and GV research proyects: 035.321-0046/93.     

On an instance of the inverse shortest paths problem

The inverse shortest paths problem in a graph is considered, that is, the problem of recovering the arc costs given some information about the shortest paths in the graph. The problem is first motivated by some practical examples arising from applications. An algorithm based on the Goldfarb-Idnani method for convex quadratic programming is then proposed and analyzed for one of the instances of the problem. Preliminary numerical results are reported.     

Evaluation of moments and their application in Hückel molecular orbital theory

Moments of acyclic carbon chains are treated in a systematic way. Explicit formulas in terms of connectivities are tabulated up to ₁₄. This facilitates the evaluation of moments by simply counting the numbers of various fragments involved. The total electron energy is analyzed by means of moments and the meaning of additivity is interpreted. An approximate formula for E is parametrized by truncation, preserving only five bond parameters. Based on these, we attempt to better rationalize and reformulte the concept of aromaticity.Formerly used names: Kiang, Yuan-sun; Tang, Au-chin