有向图上k步可达查询处理

给定一个有向图,一个k步可达查询u→?kv用来回答在该图中是否存在一条从顶点u到顶点v且长度不大于k的有向路径。k步可达查询是一种基本的图操作并在过去十年间被广泛地研究。已有的k步可达查询算法仍存在许多弊端,例如不可达查询效率低,索引规模大和索引构建时间长等。本文针对上述问题提出了2种优化方法,分别是基于互逆拓扑序号以及基于等价顶点的图压缩方法.前者提高了不可达查询的效率,后者减少了索引规模和索引构建时间。实验结果表明,本文提出的方法可以有效地处理k步可达查询,并支持大规模数据的处理。     

Enumeration of all circuits or cutsets of a graph

A computer program for the enumeration either of all the circuits or of all the cutsets of a nonoriented graph is described. It can be easily adapted for use with oriented graphs and for the enumeration of Hamilton circuits.     

A Petri net approach to enumerating all circuits of a graph

A technique utilizing the concept of reachability in Petri net is proposed to enumerate all the circuits of a graph. The proposed technique requires only vector additions on the columns of a single matrix. The present method which is a simple and applicable to both directed and undirected graphs, can easily be computerised.     

有向图在关系数据理论中的应用

针对关系数据理论中如闭包、最小函数依赖集的求解、BCNF的分解等算法表达相对抽象的情况,提出将图论中的有向图引入到函数依赖的表达之中,运用有向图的图像变换及算法来进行关系数据理论相关问题的处理,使得其表达、求解过程更为直观、简洁,更容易理解和接受。     

Simple enumeration of minimal cutsets of acyclic directed graph

Two methods are given that use combinations of nodes to enumerate all minimal cutsets. One simply has to enumerate all combinations of orders 1 to N-3 of nodes from 2 to N-1, where N is the total number of nodes. Collecting only those symbols of links of first row of adjacency matrix and in the rows given in a combination that are not in the columns of the combination, a cutset of an acyclic directed graph having all adjacent nodes is obtained. To obtain the cutsets of a general acyclic directed graph, four rules are given for deletion of those combinations that yield redundant and nonminimal subsets. The rules provide a reduced set of combinations, which then gives rise to minimal cutsets of a general graph. Three examples illustrate the algorithms     

Generation of simple limit cycles in digital circuits

Readily predictable elementary limit cycles can be generated using a first-order digital circuit subject to magnitude truncation that is excited by constant inputs. Conditions for sustaining specific length and magnitude of limit cycles are given. The results will be useful for educational demonstrations and for hardware testing of certain digital circuits.     

Generation of directed cotrees formulated in Wang's algebra

The construction of a directed graph for a network described by an impedance matrix is presented. This graph has a structure similar to that of the network. The analysis is based on the generation of directed cotrees, which are dual to the directed trees.     

Duality principle for asynchronous control circuits for directed graphs

The directed graph provides a means of analysing parallel computer structures, whether implemented in hardware or software. This letter discusses the asynchronous circuit modules used to implement the control section of such systems, and indicates a duality principle that permits a wider variety of control functions to be envisaged.     

Node-to-node error sensitivity analysis using a graph based approach for VLSI logic circuits

Shrinking the transistors size and supply voltage in the advanced VLSI logic circuits, significantly increases the susceptibility of the circuits to soft errors. Therefore, analysis of the effects on other nodes, caused by the soft errors occurring at each individual node is an essential step for VLSI logic circuit design. In this paper, a novel approach based on the Mason’s gain formula, for the node-to-node sensitivity analysis of logic circuits is proposed. Taking advantage of matrix sparsity, the runtime and the memory requirement of the proposed approach become scalable. Also, taking the effects of reconvergent paths into account, the accuracy of the proposed approach is improved considerably. According to the simulation results, the proposed approach runs 4.7× faster than those proposed in the prior works while its computational complexity is O(N^1.07) on the average.     

AN EFFICIENT CIRCUIT VECTOR SPACE ALGORITHM FOR GENERATING ALL DIRECTED CIRCUITS OF A DIGRAPH

An efficient circuit vector space algorithm is presented for enumerating directed circuits ofa directed graph,by which every directed circuit is generated by the ring sum of a fundamental circuit anda subset of the obtained directed circuits,and can be expressed as a linear combination of a basic set of thedirected circuits.     

Enumeration of all simple paths in a directed graph using Petri net: A systematic approach

The determination of all simple (or success) paths between two specified nodes in a directed graph finds various applications in graph theory, reliability evaluation of a system, etc. Many attempts at the problem of determining the S-T paths (simple or success paths between specified nodes S and T) have appeared in the literature [1–3]. The present paper, which utilizes the concept of the Petri net (PN), is yet another attempt at the same problem. The proposed technique is simple and tackles the problem in a systematic way. It is amenable to computer implementation.     

Generation of simple paths of graph by decomposition

The letter presents a method for the generation of simple paths by decomposing the given graph into two subgraphs. In this way, the simple specific subpaths can be found simultaneously in the subgraphs and their unions of Cartesian products give the desired original simple paths.     

基于有向无环图的区间覆盖率求解算法

给定一个有向无环图,回答可达性查询是图的基本操作之一.虽然很多方法使用树区间来加速可达查询的处理速度,但并不明确使用多少个区间比较合适.本文提出一种快速计算区间覆盖率的算法,该方法通过使用有效的剪枝策略来支持高效的覆盖率计算.基于所得到的区间覆盖率,可针对不同数据图确定合适的区间个数,以便在加速查询处理的同时,降低索引...     

A graph based approach for reliability analysis of nano-scale VLSI logic circuits

Advances in nano-electronics VLSI manufacturing technology and the rapid downscaling of the size of logic circuits have made them more prone to errors. This has led to the need for fast circuit reliability evaluation of large logic circuits. In this paper a new method for reliability analysis of VLSI logic circuits based on a modified form of Mason’s rule is proposed. Utilizing matrix sparsity significantly increases the speed and reduces the required memory of the proposed approach. In addition, an approach is introduced to mitigate the effect of reconvergent paths. Simulation results indicate that the proposed method is scalable and runs 4× faster than previously proposed schemes.     

Generation and evaluation of current and logic tests for switch-level sequential circuits

This article presents an approach to developing high quality tests for switch-level circuits using both current and logic test generation algorithms. Faults that are aborted or undetectable by logic tests may be detected by current tests, or vice versa. An efficient switch level test generation algorithm for generating current and logic tests is introduced. Clear definitions for analyzing the effectiveness of the joint test generation approach are derived. Experimental results are presented for demonstrating high coverage of stuck-at, stuck-on, and stuck-open faults for switch level circuits when both current and logic tests are used.This is expanded version of the work originally presented at the 1991 International Test Conference.     

Generation of transient response of nonlinear bipolar transistor circuits from device fabrication data

Dynamic models of double diffused bipolar transistors are generated from device fabrication data. The models consist of interconnections of two- and three-terminal resistors and capacitors whose characteristics are expressed in the form of tabulated values describing piecewise-linear surfaces. A circuit analysis program based on a piecewise-linear approach, simulates the time responses of circuits in which the transistors are imbedded. DC and small-signal AC analyses are also obtained. The computer program package thus yields overall circuit responses with fabrication data as input.     

Characteristics of driver and receiver circuits with a passivetransmission line in RSFQ circuits

We report simulated results of-rapid single flux quantum (SFQ) circuits having driver, receiver, and passive transmission lines for propagating SFQ pulses to investigate the design criteria. We have studied the equivalent input/output resistance of the driver/receiver in various bias conditions and found that the resistance is almost proportional to the bias current of the driver/receiver. Furthermore, we have proposed inserting a series resistor at the end of the superconducting passive transmission line (PTL) for avoiding undesirable flux trapping in the loop and for isolation in regard to the DC current. We also found that the reduction of the bias margin due to the resistance is rather small when the resistance is much smaller than the impedance of the PTL. An operating margin of more than 30% was obtained in the driver/receiver circuits including the PTL and the series resistor     

Distortion in class a transistor-amplifier circuits

When designing transistor amplifiers it is often desirable to estimate the distortion which will be introduced by the transistors. This note is concerned with transistors operating in class A conditions in wideband circuits. A simple method is given by which the maximum level of second-harmonic distortion can be calculated, and some measurements which confirm the theory are presented.     

Enumeration of success paths in a graph

A computer program for the enumeration of all success paths between a specified pair of nodes in a probablistic non-oriented graph is described. It can be easily adapted for use with oriented graphs.