Computing the local metric dimension of a graph from the local metric dimension of primary subgraphs

For an ordered subset W= w₁, w₂,?…?w_k of vertices and a vertex u in a connected graph G, the representation of u with respect to W is the ordered k-tuple r(u|W)=(d(u, w₁), d(u, w₂),?…?, d(u, w_k)), where d(x, y) represents the distance between the vertices x and y. The set W is a local metric generator for G if every two adjacent vertices of G have distinct representations. A minimum local metric generator is called a local metric basis for G and its cardinality the local metric dimension of G. We show that the computation of the local metric dimension of a graph with cut vertices is reduced to the computation of the local metric dimension of the so-called primary subgraphs. The main results are applied to specific constructions including bouquets of graphs, rooted product graphs, corona product graphs, block graphs and chain of graphs.     

Computing with graphs and graph transformations

Many software applications require the construction and manipulation of graphs. In standard programming languages, this is accomplished using low‐level mechanisms such as pointer manipulation or array indexing. In contrast, graph productions are a convenient high‐level visual notation for coding graph modifications. A graph production replaces one subgraph by another subgraph. Graph productions can define a graph grammar and graph language, or can directly transform an input graph into an output graph. Graph transformation has been applied in many areas, including the definition of visual languages and their tools, the construction of software development environments, the definition of constraint programming algorithms, the modeling of distributed systems, and the construction of neural networks. One application is presented in detail: the interpretation of mathematical notation in scanned document images. The graph models the set of mathematical symbols, and their spatial and logical relationships. This graph is transformed by productions written in the PROGRES language. Copyright © 1999 John Wiley & Sons, Ltd.     

On vertex ranking of a starlike graph

A vertex coloring c:V→{1,2,…,t} of a graph G=(V,E) is a vertex t-ranking if for any two vertices of the same color every path between them contains a vertex of larger color. The vertex ranking number χ_r(G) is the smallest value of t such that G has a vertex t-ranking. A χ_r(G)-ranking of G is said to be an optimal vertex ranking. In this paper, we present an O(|V|+|E|) time algorithm for finding an optimal vertex ranking of a starlike graph G=(V,E). Our result implies that an optimal vertex ranking of a split graph can be computed in linear time.     

Computing Cyclomatic Complexity with Cubic Flowgraphs

Two new methods for the computation of cyclomatic complexity especially for decomposable representations are introduced. Building software by integration is a developing paradigm, especially enabled by the emerging component technologies. Decomposition of the design for a top-down approach is a prerequisite for this paradigm. Cubic flowgraphs are instrumental in providing formalisms for decomposition and integration. Cyclomatic complexity analysis of a design representation that is decomposable is the goal of this research. In addition to introducing cyclomatic complexity computation using cubic flowgraphs, preservation of cyclomatic complexity in the decomposition of the cubic flowgraph is also presented.     

Computing the isoperimetric number of a graph

Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 167–172, May–June, 1994     

Determining the number of internal stability of a graph

The number of internal stability or independence number of an undirected graph has many important applications. Computationally it belongs to the class of intractable problems known as NP-Hard. In this paper we develop a tree search algorithm to determine the ndependence number of an undirected graph. Extensive computational experience on 2400 randomly generated graphs ranging from 20% to 90% densities and from 50 to 200 vertice has shown that the proposed algorithm is very effective.     

DNA计算机原理、进展及难点（I）：生物计算机系统及其在图论中的应用

基于生化反应机理的DNA计算机模型受到科学领导内许多不同科学者们的关注与兴趣。DNA计算已经形成国际科学前沿领域内研究的一个新的热点。DNA计算机的研制需要诸如生物工程、计算机科学、数学、物理、化学、信息科学、微电子技术、激光技术以及控制科学等许多学科的共同协作攻关。该系列文章拟对DNA计算机的基本原理、研究进展DNA计算的模型以及当前研究中的难点给予研讨。该文属首篇，重点讨论了DNA计算机的基本原理，引入了生物计算系统的概念，并较系统地讨论了DNA计算模型在图与组合优化中的研究进展。     

Clique-perfectness and balancedness of some graph classes

A graph is clique-perfect if the maximum size of a clique-independent set (a set of pairwise disjoint maximal cliques) and the minimum size of a clique-transversal set (a set of vertices meeting every maximal clique) coincide for each induced subgraph. A graph is balanced if its clique-matrix contains no square submatrix of odd size with exactly two ones per row and column. In this work, we give linear-time recognition algorithms and minimal forbidden induced subgraph characterizations of clique-perfectness and balancedness of P₄-tidy graphs and a linear-time algorithm for computing a maximum clique-independent set and a minimum clique-transversal set for any P₄-tidy graph. We also give a minimal forbidden induced subgraph characterization and a linear-time recognition algorithm for balancedness of paw-free graphs. Finally, we show that clique-perfectness of diamond-free graphs can be decided in polynomial time by showing that a diamond-free graph is clique-perfect if and only if it is balanced.     

利用可信计算技术改善云计算的安全性

云计算影响了互联网上世界上任何地方远程服务器处理、数据存储和共享的方式。这种共享多种分布式资源方式,使得安全问题更加复杂化。本文分析了云计算环境下的安全服务,通过整合可信计算环境来建立云计算系统。可信计算平台模式可以提高云计算的安全性。可信计算模式重要的安全服务包括加密,认证,完整性和保密性等都可以用在云计算系统中。     

云计算与网格计算的比较

介绍了当前计算方法的发展趋势,对当前主流的云计算和网格计算两种计算方法从定义、特点方面进行了详细的阐述,并对两种技术进行深入的分析比较,最终对其异同之处进行了概括总结。     

框计算浅析

该文从框计算的概念入手,阐述了框计算实施的价值和意义,并从用户、企业等角度分析了框计算实施将造成未来互联网应用与发展的巨大变迁。     

Smoothing of cubic parametric splines

The most common curve representation in CADCAM systems of today is the cubic parametric spline. Unfortunately this curve will sometimes oscillate and cause unwanted inflexions which are difficult to deal with. This paper has developed from the need to eliminate oscillations and remove inflexions from such splines, a need which may occur for example when interpolating data measured from a model. A method for interactive smoothing is outlined and a smoothing algorithm is described which is mathematically comparable to manual smoothing with a physical spline.     

On the number of Eulerian orientations of a graph

An Eulerian orientation of an undirected Eulerian graph is an orientation of the edges of the graph such that for every vertex the in-degree is equal to the out-degree. Eulerian orientations are natural flow-like structures, and Welsh has pointed out that computing their number corresponds to evaluating the Tutte polynomial at the point (0, –2) [JVW], [Wl], and is further equivalent to evaluating ice-type partition functions in statistical physics [W2]. In this paper we resolve the complexity of counting the number of Eulerian orientations of an arbitrary Eulerian graph.We give an efficient randomized approximation algorithm for counting Eulerian orientations of any Eulerian graph. Our algorithm is based on a reduction to counting perfect matchings for a class of graphs for which the methods of Broder [B], Jerrum and Sinclair [JS1], and others [DL] [DS] apply. A crucial step of the reduction is the Monotonicity Lemma (Lemma 3.1) which is of independent combinatorial interest. Roughly speaking, the Monotonicity Lemma establishes the intuitive fact that increasing the number of constraints applied on a flow problem cannot increase the number of solutions. The proof of the lemma involves a new decomposition technique which decouples problematically overlapping structures (a recurrent obstacle in handling large combinatorial populations) and allows detailed enumeration arguments. As a by-product, we exhibit a class of graphs for which perfect and near-perfect matchings are polynomially related, and hence the permanent can be approximated, for reasons other than short augmenting paths (previously the only known approach).We also give the complementary hardness result, namely, that counting exactly Eulerian orientations is #P-complete. Finally, we provide some connections with counting Euler tours.     

Computing constant offsets of a NURBS B-Rep

An approach for the automatic offset of a NURBS B-Rep has been presented which can be used for a class of manifold B-Reps. The approach offsets each of the trimmed surfaces (faces) of the B-Rep and then removes the gaps and intersections between offset faces automatically, if any. The offset B-Rep is then created by sewing all the updated offset faces. The practical approach and the treatment of the subject presented are unique and have not been reported earlier. The approach works under the assumption that the number of faces in both base and offset B-Reps is the same. It further assumes that the faces are at least G₁ continuous and non-self intersecting after constant offset. The present approach has given accurate and robust offsets of many lay-up surfaces (B-Reps) in the composite laminate modeling. The approach has better error control. Some of the offsets of lay-up surfaces that are generated using this approach have been presented.     

自然计算的新分支——膜计算

作为自然计算的新分支,膜计算是当前计算机科学、数学、生物学和人工智能等多学科交叉的研究热点.概述膜计算的最新动态,以一个简单膜系统为例介绍膜计算的基本概念和基本原理,从细胞型、组织型和神经型三类膜系统以及它们的计算能力和计算效率方面介绍膜计算理论研究进展,通过概括膜计算国内外应用研究成果讨论其应用前景和方向,并从软硬件发展历程分析膜系统软硬实现研究现状.最后给出有关膜计算研究的重要网络资源、热点研究领域和重点关注的问题.     

On approximating the longest path in a graph

We consider the problem of approximating the longest path in undirected graphs. In an attempt to pin down the best achievable performance ratio of an approximation algorithm for this problem, we present both positive and negative results. First, a simple greedy algorithm is shown to find long paths in dense graphs. We then consider the problem of finding paths in graphs that are guaranteed to have extremely long paths. We devise an algorithm that finds paths of a logarithmic length in Hamiltonian graphs. This algorithm works for a much larger class of graphs (weakly Hamiltonian), where the result is the best possible. Since the hard case appears to be that of sparse graphs, we also consider sparse random graphs. Here we show that a relatively long path can be obtained, thereby partially answering an open problem of Broderet al. To explain the difficulty of obtaining better approximations, we also prove hardness results. We show that, for any ε<1, the problem of finding a path of lengthn-n ^ε in ann-vertex Hamiltonian graph isNP-hard. We then show that no polynomial-time algorithm can find a constant factor approximation to the longest-path problem unlessP=NP. We conjecture that the result can be strengthened to say that, for some constant δ>0, finding an approximation of ration ^δ is alsoNP-hard. As evidence toward this conjecture, we show that if any polynomial-time algorithm can approximate the longest path to a ratio of , for any ε>0, thenNP has a quasi-polynomial deterministic time simulation. The hardness results apply even to the special case where the input consists of bounded degree graphs. D. Karger was supported by an NSF Graduate Fellowship, NSF Grant CCR-9010517, and grants from the Mitsubishi Corporation and OTL. R. Motwani was supported by an Alfred P. Sloan Research Fellowship, an IBM Faculty Development Award, grants from Mitsubishi and OTL, NSF Grant CCR-9010517, and NSF Young Investigator Award CCR-9357849, with matching funds from IBM, the Schlumberger Foundation, the Shell Foundation, and the Xerox Corporation, G. D. S. Ramkumar was supported by a grant from the Toshiba Corporation. Communicated by M. X. Goemans.     

On the termination of clause graph resolution

This paper introducesextended clause graph resolution, a variant of Kowalski's clause graph resolution that is terminating at the full first-order level. This terminating variant is obtained by extending the definitions of clause graph and clause graph resolution to include more information about the interdependencies between links and clauses in the graph, by restricting purity slightly and by employing an exhaustive search of eligible links.     

Computing transparently: the independent sets in a graph

A procedure is given for finding the independent sets in an undirected graph by xeroxing onto transparent plastic sheets. Let an undirected graph having n vertices and m edges be given. A list of all the independent subsets of the set of vertices of the graph is constructed by using a xerox machine in a manner that requires the formation of only n + m + 1 successive transparencies. An accompanying list of the counts of the elements in each independent set is then constructed using only O(n ²) additional transparencies. The list with counts provides a list of all maximum independent sets. This gives an O(n ²) step solution for the classical problem of finding the cardinality of a maximal independent set in a graph. The applicability of these procedures is limited, of course, by the increase in the information density on the transparencies when n is large. Our ultimate purpose here is to give hand tested ‘ultra parallel’ algorithmic procedures that may prove suitable for realization using future optical technologies.     

新型样条权函数神经网络的云计算研究

采用权函数训练神经网络是近些年发展起来的一种算法.该算法有许多优点,例如可以直接求得全局最优点,有很好的泛化能力,训练后的权函数能够反映隐含在样本内部的有价值的信息特征等.因此进一步提高算法效率就显得十分重要.为了进一步提高运算速度,文中将神经网络与云计算相结合,采用云计算服务对一种新型的三次样条权函数神经网络算法的性能进行了分析,提出了云计算的定义,研究了三次样条权函数神经网络算法的并行机制.结果表明,采用云计算能够大幅提高三次样条权函数神经网络算法的效率.