Maintaining Regular Properties Dynamically in k-Terminal Graphs

The t -topology tree data structure is developed for maintaining t -ary trees dynamically. Each of a certain set of tree operations is shown to take O(log n) time, where n is the number of vertices in the trees. The t -topology trees are used to maintain any given regular property on members of the family of k -terminal graphs under a variety of dynamic graph operations. Received February 1994; revised February 1995.     

Decision tree complexity of graph properties with dimension at most 5

A graph property is a set of graphs such that if the set contains some graph G then it also contains each isomorphic copy of G(with the same vertex set).A graph propoerty P on n vertices is said to be elusive,if every decision tree algorithm recognizing P must examine all n(n-1)/2 paris of vertices in the worst case.Karp conjectured that every nontrivial monotone graph property is elusive,In this paper,this conjecture is proved for some cases,Especially,it is shown that if the abstract simplicial complex of a nontrivial monotone graph property P has dimension not exceeding 5, then P is elusive.     

Perfect stables in graphs

A perfect stable in a graph G is a stable S with the property that any vertex of G is either in S or adjacent with at least two vertices which are in S. This concept is an obvious generalization of the notion of perfect matching. In this note, the problem of deciding if a given graph has a perfect stable is considered. This problem is shown to be in general NP-complete, but polynomial for K_1,3-free graphs.     

边赋权森林ω-路划分的O(n)算法

ω-路划分问题是路划分问题的一般化,它源于并行计算机系统、计算机网络与分布式控制系统等一类广播通信问题.设置最少的信息源节点,使得在指定的时间内将信息源节点所拥有的信息发送到其余节点,并且保证不同通信线路之间不得相交.从Hamilton路的NP-完全性不难看出,ω-路划分问题属于NP-完全问题.通过构造性证明技术,获得了边赋非负权路径、树和森林的ω-路划分问题的一些性质.分别提出了求解边赋非负权路径和边赋非负权树的ω-路划分问题的线性时间算法,讨论了算法的局部实现技术,详细地分析了这些算法的复杂度.以这两个算法为基础,提出了一个线性时间算法求解边赋非负权森林的ω-路划分问题.所提出的算法直观简明、操作容易,只需要较少的运行时间和较小的存储空间.     

A graph approach to generate all possible regression submodels

A regression graph to enumerate and evaluate all possible subset regression models is introduced. The graph is a generalization of a regression tree. All the spanning trees of the graph are minimum spanning trees and provide an optimal computational procedure for generating all possible submodels. Each minimum spanning tree has a different structure and characteristics. An adaptation of a branch-and-bound algorithm which computes the best-subset models using the regression graph framework is proposed. Experimental results and comparison with an existing method based on a regression tree are presented and discussed.     

Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes

Fault-tolerant broadcasting and secure message distribution are important issues for numerous applications in networks. It is a common idea to design multiple spanning trees with a specific property in the underlying graph of a network to serve as a broadcasting scheme or a distribution protocol for receiving high levels of fault-tolerance and of security. A set of spanning trees in a graph is said to be edge-disjoint if these trees are rooted at the same node without sharing any common edge. Hsieh and Tu [S.-Y. Hsieh, C.-J. Tu, Constructing edge-disjoint spanning trees in locally twisted cubes, Theoretical Computer Science 410 (2009) 926-932] recently presented an algorithm for constructing n edge-disjoint spanning trees in an n-dimensional locally twisted cube. In this paper, we prove that indeed all spanning trees constructed by their algorithm are independent, i.e., any two spanning trees are rooted at the same node, say r, and for any other node v≠r, the two different paths from v to r, one path in each tree, are internally node-disjoint.     

一种查询XML异构数据源的新方法

由于异构数据源存在结构差异和结构不兼容等问题,在其上进行查询是一个挑战.本文根据XML树的特点,对其进行了外延,设计了一种新的XML树的查询方法.通过样式图获得XML树的结点间的语义关系,查询条件可以表示为XML样式图模式,查询不被限定于特定的XML树,给出了基于样式图模式的查询算法.用例说明了该方法如何应用于异构数据源的查询.     

Optimal design of flat patterns for 3D folded structures by unfolding with topological validation

There are applications in the sheet metal, paperboard, packaging and various other industries for the computer-aided design of flat patterns for folding into some desired 3D folded structure made of piecewise flat faces. This paper describes a methodology for the automatic development of flat patterns for any given folded structure based on enumerating all possible spanning trees of the face adjacency graph (the graph that represents the connectivity among the faces of the structure) since any spanning tree represents a potential topological unfolding of that structure. Complications found in non-manifold structures, such as where more than two faces are joined at one common edge, are also addressed in this work by way of recognizing topologically invalid spanning trees. Furthermore, a strategy is also developed to detect overlapping of faces within the pattern purely by checking its topology defined in the spanning tree, without first having to geometrically construct the pattern layout. Finally, three measures of compactness are adopted as the optimality criteria for the methodology to output flat pattern results ranked according to their compactness. The procedure is implemented as a computer program and applied to six example structures in this paper to illustrate the capabilities of the methodology.     

A hierarchy of the class of apex NLC graph languages by bounds on the number of nonterminal nodes in productions

 In this paper, we consider derivation trees in apex NLC graph languages. We show that for every graph H in arbitrary apex NLC graph language, a decomposition tree of H can be constructed from a derivation tree of H. We also show that there exists a hierarchy in the class of apex NLC graph languages when we restrict the number of nonterminals in the right-hand sides of productions in apex NLC graph grammars. Received: 5 July 1994/12 February 1996     

图的树分解算法及其应用

一个图G=(V,E)的树分解是将结点集V的子集作为树T的节点,使得在T上任意一条路径上的两个端节点的交集包含于该路径上的任意一个节点中。将T上最小(节点)对应子集的元素个数减1定义为分解树T的宽度,用宽度最小的分解树T的树宽度定义图G的树宽度。一个合取范式(Conjunctive Normal Form,CNF)公式F可以用一个二分图G=(V∪C,E)表示(公式的因子图),其中变元结点集V对应公式F中的变元集,子句结点集C对应公式F中的子句集,变元在子句中的正(负)出现用实(虚)边表示。忽略公式因子图中边上的符号,得到一个二分图。文中研究了图的树分解算法,并将树分解算法应用到CNF公式的因子图树分解。通过实验观察公式因子图的树宽度与求解难度之间的联系。     

Decision trees for hierarchical multi-label classification

Hierarchical multi-label classification (HMC) is a variant of classification where instances may belong to multiple classes at the same time and these classes are organized in a hierarchy. This article presents several approaches to the induction of decision trees for HMC, as well as an empirical study of their use in functional genomics. We compare learning a single HMC tree (which makes predictions for all classes together) to two approaches that learn a set of regular classification trees (one for each class). The first approach defines an independent single-label classification task for each class (SC). Obviously, the hierarchy introduces dependencies between the classes. While they are ignored by the first approach, they are exploited by the second approach, named hierarchical single-label classification (HSC). Depending on the application at hand, the hierarchy of classes can be such that each class has at most one parent (tree structure) or such that classes may have multiple parents (DAG structure). The latter case has not been considered before and we show how the HMC and HSC approaches can be modified to support this setting. We compare the three approaches on 24 yeast data sets using as classification schemes MIPS’s FunCat (tree structure) and the Gene Ontology (DAG structure). We show that HMC trees outperform HSC and SC trees along three dimensions: predictive accuracy, model size, and induction time. We conclude that HMC trees should definitely be considered in HMC tasks where interpretable models are desired.     

Hierarchy Theorems for Property Testing

Referring to the query complexity of property testing, we prove the existence of a rich hierarchy of corresponding complexity classes. That is, for any relevant function q, we prove the existence of properties that have testing complexity Θ(q). Such results are proven in three standard domains often considered in property testing: generic functions, adjacency predicates describing (dense) graphs, and incidence functions describing bounded-degree graphs. While in two cases, the proofs are quite straightforward, and the techniques employed in the case of the dense graph model seem significantly more involved. Specifically, problems that arise and are treated in the latter case include (1) the preservation of distances between graph under a blow-up operation and (2) the construction of monotone graph properties that have local structure.     

王氏代数的推论和m阶全图的树的数量表达式

在文献［１］提出的求一个图的全部树的方法中，王氏代数被用以筛除相关元素（相关树支）。此文将进一步讨论王氏代数的有关定义和运算规则，给出了部分相关和子相关符号向量等概念。文中提出的４个推论使王氏代数得以在求图的树的算法中得到系统的应用。在分析了ｍ阶全图的关联矩阵的特性后，定理１给出了其具有的树数量的表达式。     

基于主干子图的幂律特征图聚类算法

从Internet拓扑的幂律特征（度分布律）出发,定义了主干子图的相关概念,证明了主干子图的若干性质,并在此基础上给出了基于主干子图的聚类算法。该算法可应用于有幂律特征的大型图的混合布局,也可为幂律特征网络的研究提供参考。幂律特征图可以被分解为一个主干子图和多个子树。主干子图是一些度相对较高节点的集合;而子树则正好相反,幂律特征有效地保证了节点度分布的非均一特性。基于主干子图理论的图聚类算法可以分成两个步骤,即主干子图生成算法和桩树生成算法。主干子图Gs(Vs,Es)与原始图G(V,E)之间的同态等价关系     

Time-varying contour topology

The contour tree has been used to compute the topology of isosurfaces, generate a minimal seed set for accelerated isosurface extraction, and provide a user interface to segment individual contour components in a scalar field. In this paper, we extend the benefits of the contour tree to time-varying data visualization. We define temporal correspondence of contour components and describe an algorithm to compute the correspondence information in time-dependent contour trees. A graph representing the topology changes of time-varying isosurfaces is constructed in real-time for any selected isovalue using the precomputed correspondence information. Quantitative properties, such as surface area and volume of contour components, are computed and labeled on the graph. This topology change graph helps users to detect significant topological and geometric changes in time-varying isosurfaces. The graph is also used as an interactive user interface to segment, track, and visualize the evolution of any selected contour components over time.     

An optimal emulator and VLSI layout for complete binary trees

How complex does a graph need to be in order to emulate an arbitrary size complete binary tree with the same level of efficiency as would be obtained by a directed complete graph? In this paper, this question is answered by showing that any -node graph needs to have at least edges in order to perform this emulation. Subsequently, a graph is presented which meets this bound, and it is shown how to optimally embed an arbitrary size complete binary tree in the proposed graph. It is also shown how to optimally embed a node cycle in the proposed graph of nodes with unit dilation, unit congestion and uniform load of . Finally optimal VLSI layouts are presented for the proposed graph which require asymptotically same area as the corresponding layouts for complete binary trees. Received: 7 July 1994 / 28 May 1996     

数据关联的粒化树描述方法

为探讨数据关联问题,对数据集实施分层粒化处理,得到分层结构的粒化树.进而利用粒化树的层次信息和粒度的数值表示,并通过关联数据产生的数据联系,给出两棵粒化树之间数据关联的定义.文中视上近似为算子,借助上近似运算对应的粒,获得数据关联的判定定理,并基于粒度的数值信息判定关联紧密程度,形成数据关联的粒化树描述方法,其展示的粒化分层和粒度数值表示可看作粒计算研究的一种形式.实例的讨论表明粒化树方法的应用价值     

Lower bounds and exact algorithms for the quadratic minimum spanning tree problem

We address the quadratic minimum spanning tree problem (QMSTP), the problem of finding a spanning tree of a connected and undirected graph such that a quadratic cost function is minimized. We first propose an integer programming formulation based on the reformulation–linearization technique (RLT). We then use the idea of partitioning spanning trees into forests of a given fixed size and obtain a QMSTP reformulation that generalizes the RLT model. The reformulation is such that the larger the size of the forests, the stronger lower bounds provided. Thus, a hierarchy of formulations is obtained. At the lowest hierarchy level, one has precisely the RLT formulation, which is already stronger than previous formulations in the literature. The highest hierarchy level provides the convex hull of integer feasible solutions for the problem. The formulations introduced here are not compact, so the direct evaluation of their linear programming relaxation bounds is not practical. To overcome that, we introduce two lower bounding procedures based on Lagrangian relaxation. These procedures are embedded into two parallel branch-and-bound algorithms. As a result of our study, several instances in the literature were solved to optimality for the first time.     

MGV: a system for visualizing massive multidigraphs

Describes MGV (Massive Graph Visualizer), an integrated visualization and exploration system for massive multidigraph navigation. It adheres to the visual information-seeking mantra: overview first, zoom and filter, then details on demand. MGV's only assumption is that the vertex set of the underlying digraph corresponds to the set of leaves of a pre-determined tree T. MGV builds an out-of-core graph hierarchy and provides mechanisms to plug in arbitrary visual representations for each graph hierarchy slice. Navigation from one level to another of the hierarchy corresponds to the implementation of a drill-down interface. In order to provide the user with navigation control and interactive response, MGV incorporates a number of visualization techniques like interactive pixel-oriented 2D and 3D maps, statistical displays, color maps, multi-linked views and a zoomable label-based interface. This makes the association of geographic information and graph data very natural. To automate the creation of the vertex set hierarchy for MGV, we use the notion of graph sketches. They can be thought of as visual indices that guide the navigation of a multigraph too large to fit on the available display. MGV follows the client-server paradigm and it is implemented in C and Java-3D. We highlight the main algorithmic and visualization techniques behind the tools and, along the way, point out several possible application scenarios. Our techniques are being applied to multigraphs defined on vertex sets with sizes ranging from 100 million to 250 million vertices     

Partitioning trees: Matching,domination, and maximum diameter

A matching and a dominating set in a graph G are related in that they determine diameter-bounded subtree partitions of G. For a maximum matching and a minimum dominating set, the associate partitions have the fewest numbers of trees. The problem of determining a minimum dominating set in an arbitrary graph G is known to be NP-complete. In this paper we present a linear algorithm for partitioning an arbitrary tree into a minimum number of subtrees, each having a diameter at mostk, for a givenk.Research supported in part by the National Science Foundation under Grant ENG 7902960.Research supported in part by the National Science Foundation under Grant STI 7902960.