Branch-bonds,two-factors in iterated line graphs and circuits in weighted graphs

A nontrivial path is called a branch if it has only internal vertices of degree two and end vertices of degree not two. A set S of branches of a graph G is called a branch cut if the deletion of all edges and internal vertices of branches of S results in more components than G. A minimal branch cut is called a branch-bond. In this paper, we found some relationships amongst branch-bonds, weighted graphs and two-factors in iterated line graphs. We also obtained some bounded number of components in two-factor of iterated line graphs by using the concept of branch-bonds.     

Grammars on partial graphs

Summary The concept of Chomsky-grammars is generalized to graph-grammars; the gluing of graphs is defined by a pushout-construction. In the present paper, we allow the left-hand and right-hand side of a production to be partial graphs, i.e. graphs in which there may be edges without a source or target node. A necessary and sufficient condition for applicability of productions is given. Furthermore, convex graph-grammars are studied.     

值域为坡代数的加权图和模糊图的范畴关系

坡代数是元素的乘法小于等于每个因子的加法幂等的半环。以坡代数为取值域,证明了加权图范畴可以作为余反射子范畴嵌入到模糊图范畴中去;如果坡代数的乘法有单位元,则这种嵌入还具有反射性。     

Minimum cycle bases of weighted outerplanar graphs

We give the first optimal algorithm that computes a minimum cycle basis for any weighted outerplanar graph. Specifically, for any n-node edge-weighted outerplanar graph G, we give an O(n)-time algorithm to obtain an O(n)-space compact representation Z(C) for a minimum cycle basis C of G. Each cycle in C can be computed from Z(C) in O(1) time per edge. Our result works for directed and undirected outerplanar graphs G.     

Maximumk-covering of weighted transitive graphs with applications

Consider a weighted transitive graph, where each vertex is assigned a positive weight. Given a positive integerk, the maximumk-covering problem is to findk disjoint cliques covering a set of vertices with maximum total weight. An 0(kn ²)-time algorithm to solve the problem in a transitive graph is proposed, wheren is the number of vertices. Based on the proposed algorithm the weighted version of a number of problems in VLSI layout (e.g.,k-layer topological via minimization), computational geometry (e.g., maximum multidimensionalk-chain), graph theory (e.g., maximumk-independent set in interval graphs), and sequence manipulation (e.g., maximum increasingk-subsequence) can be solved inO(kn ²), wheren is the input size.This Work was supported in part by the National Science Foundation under Grant MIP-8709074 and MIP-8921540.     

A characterization of complete bipartite RAC graphs

A Right Angle Crossing drawing (RAC drawing for short) of a graph is such that edges can only cross at an angle of . In this paper we provide a characterization of the complete bipartite graphs that admit a straight-line RAC drawing.     

Ranking weighted clustering coefficient in large dynamic graphs

Efficiently searching top-k representative vertices is crucial for understanding the structure of large dynamic graphs. Recent studies show that communities formed by a vertex with high local clustering coefficient and its neighbours can achieve enhanced information propagation speed as well as disease transmission speed. However, local clustering coefficient, which measures the cliquishness of a vertex in its local neighbourhood, prefers vertices with small degrees. To remedy this issue, in this paper we propose a new ranking measure, weighted clustering coefficient (WCC) of vertices, by integrating both local clustering coefficient and degree. WCC not only inherits the properties of local clustering coefficient but also approximately measures the density (i.e., average degree) of its neighbourhood subgraph. Thus, vertices with higher WCC are more likely to be representative. We study efficiently computing and monitoring top-k representative vertices based on WCC over large dynamic graphs. To reduce the search space, we propose a series of heuristic upper bounds for WCC to prune a large portion of disqualifying vertices from the search space. We also develop an approximation algorithm by utilizing Flajolet-Martin sketch to trade acceptable accuracy for enhanced efficiency. An efficient incremental algorithm dealing with frequent updates in dynamic graphs is explored as well. Extensive experimental results on a variety of real-life graph datasets demonstrate the efficiency and effectiveness of our approaches.     

Vertex rankings of chordal graphs and weighted trees

In this paper we consider the vertex ranking problem of weighted trees. We show that this problem is strongly NP-hard. We also give a polynomial-time reduction from the problem of vertex ranking of weighted trees to the vertex ranking of (simple) chordal graphs, which proves that the latter problem is NP-hard. In this way we solve an open problem of Aspvall and Heggernes. We use this reduction and the algorithm of Bodlaender et al.'s for vertex ranking of partial k-trees to give an exact polynomial-time algorithm for vertex ranking of a tree with bounded and integer valued weight functions. This algorithm serves as a procedure in designing a PTAS for weighted vertex ranking problem of trees with bounded weight functions.     

Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs

An efficient dominating set (or perfect code) in a graph is a set of vertices the closed neighborhoods of which partition the vertex set of the graph. The minimum weight efficient domination problem is the problem of finding an efficient dominating set of minimum weight in a given vertex-weighted graph; the maximum weight efficient domination problem is defined similarly. We develop a framework for solving the weighted efficient domination problems based on a reduction to the maximum weight independent set problem in the square of the input graph. Using this approach, we improve on several previous results from the literature by deriving polynomial-time algorithms for the weighted efficient domination problems in the classes of dually chordal and AT-free graphs. In particular, this answers a question by Lu and Tang regarding the complexity of the minimum weight efficient domination problem in strongly chordal graphs.     

Dynamic consensus estimation of weighted average on directed graphs

Recent applications call for distributed weighted average estimation over sensor networks, where sensor measurement accuracy or environmental conditions need to be taken into consideration in the final consensused group decision. In this paper, we propose new dynamic consensus filter design to distributed estimate weighted average of sensors’ inputs on directed graphs. Based on recent advances in the filed, we modify the existing proportional-integral consensus filter protocol to remove the requirement of bi-directional gain exchange between neighbouring sensors, so that the algorithm works for directed graphs where bi-directional communications are not possible. To compensate for the asymmetric structure of the system introduced by such a removal, sufficient gain conditions are obtained for the filter protocols to guarantee the convergence. It is rigorously proved that the proposed filter protocol converges to the weighted average of constant inputs asymptotically, and to the weighted average of time-varying inputs with a bounded error. Simulations verify the effectiveness of the proposed protocols.     

权长相合的带权无向图画图算法

针对带权无向图的输出需用边长反映权值大小的问题,提出了一种基于遗传算法的带权无向图画图算法,通过对顶点坐标的编码进行交叉和变异来得到理想的节点坐标,变异算子结合了非一致性变异和单点邻域变异,并在适应度函数中运用顶点平均距离、边交叉数、多度顶点相关边夹角均匀度、边的权值长度比一致程度四个美学标准。实验结果表明,该算法画出的图形连线无交叉,分支清晰,权值—长度相合,能得到清晰、美观且能直观反映权值的可视化输出结果,可应用于带权无向图的可视化输出系统的设计。     

A good characterization of squares of strongly chordal split graphs

The square H² of a graph H is obtained from H by adding new edges between every two vertices having distance two in H. Lau and Corneil [Recognizing powers of proper interval, split and chordal graphs, SIAM J. Discrete Math. 18 (2004) 83-102] proved that recognizing squares of split graphs is an NP-complete problem. In contrast, we show that squares of strongly chordal split graphs can be recognized in quadratic-time by giving a structural characterization of these graph class.     

Programs as partial graphs II: Recursion

In Part I of the paper, we have proposed a unified relational algebra approach using partial graphs for theoretical investigations on semantics, correctness and termination. This approach is extended here to systems of recursive programs, allowing not only sequencing and conditional branching as a control structure but also flow diagrams.An equivalence proof of operational and denotational semantics is obtained which is strictly based on axioms of relational algebra. A short new proof of an important completeness result is given in the generalized setting of systems of recursive flow diagram programs. Finally, Hitchcock-Park's theorem on derivatives is formulated in the general case of nondeterministic recursive flow diagram programs.     

A characterization of database graphs admitting a simple locking protocol

Summary A simple locking protocol is presented for transactions executing concurrently in a database. The locking protocol is not two-phase, but each entity in the database may be locked at most once by any transaction. The database is modeled by a directed graph whose vertices correspond to the entities, and whose arcs correspond to certain locking restrictions. Necessary and sufficient conditions which assure serializability and deadlock-freedom in the absence of a concurrency control are derived.     

On axiomatic characterization of weighted entropy

In this paper, we have characterized weighted entropy of type (α,β) under a suitable set of axioms. Some properties of this measure have also been studied.     

Fractal characterization of speech waveform graphs

Mandelbrot's fractal geometry has provided a new qualitative and quantitative approach for understanding the complex shapes of nature. In this paper, the fractal structure of speech waveforms is studied at time scales where important phonetic and prosodic information reside. We have found, using methods commonly applied to complex shapes such as coastlines, that speech exhibits fractal characteristics. We have made measurements of the fractal dimension (D) for sentences and have found that D ∼ 1.66 with little change between speakers and sentences.     

A limit characterization for the number of spanning trees of graphs

In this paper we propose a limit characterization of the behaviour of classes of graphs with respect to their number of spanning trees. Let {G_n} be a sequence of graphs G₀,G₁,G₂,… that belong to a particular class. We consider graphs of the form K_n−G_n that result from the complete graph K_n after removing a set of edges that span G_n. We study the spanning tree behaviour of the sequence {K_n−G_n} when n→∞ and the number of edges of G_n scales according to n. More specifically, we define the spanning tree indicator ({G_n}), a quantity that characterizes the spanning tree behaviour of {K_n−G_n}. We derive closed formulas for the spanning tree indicators for certain well-known classes of graphs. Finally, we demonstrate that the indicator can be used to compare the spanning tree behaviour of different classes of graphs (even when their members never happen to have the same number of edges).