Fully dynamic biconnectivity in graphs

We present an algorithm for maintaining the biconnected components of a graph during a sequence of edge insertions and deletions. It requires linear storage and preprocessing time. The amortized running time for insertions and for deletions isO(m ^2/3 ), wherem is the number of edges in the graph. Any query of the form ‘Are the verticesu andv biconnected?’ can be answered in timeO(1). This is the first sublinear algorithm for this problem. We can also output all articulation points separating any two vertices efficiently. If the input is a plane graph, the amortized running time for insertions and deletions drops toO(√n logn) and the query time isO(log² n), wheren is the number of vertices in the graph. The best previously known solution takes timeO(n ^2/3 ) per update or query.     

Dynamic bottleneck optimization for k-edge and 2-vertex connectivity

We consider the problem of updating efficiently the minimum value b over a weighted graph, so that edges with a cost less than b induce a spanning subgraph satisfying a k-edge or 2-vertex connectivity constraint, when the cost of an edge of the graph is updated. Our results include update algorithms of almost linear time (up to poly-logarithmic factors) in the number of vertices for all considered connectivity constraints (for fixed k), and a worst case construction showing that these algorithms are almost optimal in their class.     

Maintaining bridge-connected and biconnected components on-line

We consider the twin problems of maintaining the bridge-connected components and the biconnected components of a dynamic undirected graph. The allowed changes to the graph are vertex and edge insertions. We give an algorithm for each problem. With simple data structures, each algorithm runs inO(n logn +m) time, wheren is the number of vertices andm is the number of operations. We develop a modified version of the dynamic trees of Sleator and Tarjan that is suitable for efficient recursive algorithms, and use it to reduce the running time of the algorithms for both problems toO(m(m,n)), where is a functional inverse of Ackermann's function. This time bound is optimal. All of the algorithms useO(n) space.Research at Princeton University supported in part by National Science Foundation Grant DCR-86-05962 and Office of Naval Research Contract N00014-91-J-1463.This work was partially done while the author was at the Department of Computer Science, Princeton University, Princeton, NJ 08544, USA.     

Spanners in sparse graphs

A t-spanner of a graph G is a spanning subgraph S in which the distance between every pair of vertices is at most t times their distance in G. If S is required to be a tree then S is called a tree t-spanner of G. In 1998, Fekete and Kremer showed that on unweighted planar graphs deciding whether G admits a tree t-spanner is polynomial time solvable for t?3 and is NP-complete when t is part of the input. They also left as an open problem if the problem is polynomial time solvable for every fixed t?4. In this work we resolve the open question of Fekete and Kremer by proving much more general results:

• • 

  The problem of finding a t-spanner of treewidth at most k in a given planar graph G is fixed parameter tractable parameterized by k and t. Moreover, for every fixed t and k, the running time of our algorithm is linear.

• • 

  Our technique allows to extend the result from planar graphs to much more general classes of graphs. An apex graph is a graph that can be made planar by the removal of a single vertex. We prove that the problem of finding a t-spanner of treewidth k is fixed parameter tractable on graphs that do not contain some fixed apex graph as a minor, i.e. on apex-minor-free graphs. The class of apex-minor-free graphs contains planar graphs and graphs of bounded genus.

• • 

  Finally, we show that the tractability border of the t-spanner problem cannot be extended beyond the class of apex-minor-free graphs and in this sense our results are tight. In particular, for every t?4, the problem of finding a tree t-spanner is NP-complete on K6-minor-free graphs.

     

由邻接矩阵求解可达矩阵的一种改进简便算法

传统的由邻接矩阵求解可达矩阵的算法计算量很大，不适合手动计算，也没有提出相应的适合计算机的算法。这篇文章引入转移矩阵的概念．并在此基础上加以改进，形成一套完整的可行的求解可迭矩阵的方法。有效地减少了计算量。     

Flow equivalent trees in undirected node-edge-capacitated planar graphs

Given an edge-capacitated undirected graph G=(V,E,C) with edge capacity , n=|V|, an s−t edge cut C of G is a minimal subset of edges whose removal from G will separate s from t in the resulting graph, and the capacity sum of the edges in C is the cut value of C. A minimum s−t edge cut is an s−t edge cut with the minimum cut value among all s−t edge cuts. A theorem given by Gomory and Hu states that there are only n−1 distinct values among the n(n−1)/2 minimum edge cuts in an edge-capacitated undirected graph G, and these distinct cuts can be compactly represented by a tree with the same node set as G, which is referred to the flow equivalent tree. In this paper we generalize their result to the node-edge cuts in a node-edge-capacitated undirected planar graph. We show that there is a flow equivalent tree for node-edge-capacitated undirected planar graphs, which represents the minimum node-edge cut for any pair of nodes in the graph through a novel transformation.     

Efficient processing of label-constraint reachability queries in large graphs

In this paper, we study a variant of reachability queries, called label-constraint reachability (LCR) queries. Specifically, given a label set S and two vertices u₁ and u₂ in a large directed graph G, we check the existence of a directed path from u₁ to u₂, where edge labels along the path are a subset of S. We propose the path-label transitive closure method to answer LCR queries. Specifically, we t4ransform an edge-labeled directed graph into an augmented DAG by replacing the maximal strongly connected components as bipartite graphs. We also propose a Dijkstra-like algorithm to compute path-label transitive closure by re-defining the “distance” of a path. Comparing with the existing solutions, we prove that our method is optimal in terms of the search space. Furthermore, we propose a simple yet effective partition-based framework (local path-label transitive closure+online traversal) to answer LCR queries in large graphs. We prove that finding the optimal graph partition to minimize query processing cost is a NP-hard problem. Therefore, we propose a sampling-based solution to find the sub-optimal partition. Moreover, we address the index maintenance issues to answer LCR queries over the dynamic graphs. Extensive experiments confirm the superiority of our method.     

On a simple randomized algorithm for finding a 2-factor in sparse graphs

We analyze the performance of a simple randomized algorithm for finding 2-factors in directed Hamiltonian graphs of out-degree at most two and in undirected Hamiltonian graphs of degree at most three. For the directed case, the algorithm finds a 2-factor in O(n²) expected time. The analysis of our algorithm is based on random walks on the line and interestingly resembles the analysis of a randomized algorithm for the 2-SAT problem given by Papadimitriou [On selecting a satisfying truth assignment, in: Proc. 32nd Annual IEEE Symp. on the Foundations of Computer Science (FOCS), 1991, p. 163]. For the undirected case, the algorithm finds a 2-factor in O(n³) expected time. We also analyze random versions of these graphs and show that cycles of length Ω(n/logn) can be found with high probability in polynomial time. This partially answers an open question of Broder et al. [Finding hidden Hamilton cycles, Random Structures Algorithms 5 (1994) 395] on finding hidden Hamiltonian cycles in sparse random graphs and improves on a result of Karger et al. [On approximating the longest path in a graph, Algorithmica 18 (1997) 82].     

Chain packing in graphs

This paper discusses the complexity of packingk-chains (simple paths of lengthk) into an undirected graph; the chains packed must be either vertex-disjoint or edge-disjoint. Linear-time algorithms are given for both problems when the graph is a tree, and for the edge-disjoint packing problem when the graph is general andk = 2. The vertex-disjoint packing problem for general graphs is shown to be NP-complete even when the graph has maximum degree three andk = 2. Similarly the edge-disjoint packing problem is NP-complete even when the graph has maximum degree four andk = 3.This is a revised version of the technical report [15].     

No odd pairs in minimal imperfect NP5 graphs

We prove that a minimal imperfect graph containing a vertex which is not on any induced P₅ has no odd pair.     

基于实体数据模型的空间邻接定量分析探讨*

空间邻接是一种基本的空间拓扑关系, 它对研究地理现象的分布规律和演化过程有着重要的意义。而目前许多GIS 软件所采用的空间实体数据模型并不包含拓扑信息, 故难以定量地计算、分析地理对象间的空间邻接关系。针对上述缺陷提出了基于实体数据模型的空间邻接定量分析算法, 并以MapInfo 为例予以实现, 最后以实例分析验证算法的有效性。     

细分曲面的有序邻接顶点表数据结构

细分曲面的实现过程中使用的网格数据结构都是基于边的结构,它们只是提供了一种通用的网格遍历方法;而对于细分曲面来说,基于顶点和多边形的网格表示却是更合理有效的选择。给出了一种适用于细分曲面的数据结构OAVL,它具有简便易于实现的特点,可以方便地获取网格中邻接顶点、边和面的信息,并且具有较高的空间效率,最后分析了基于OAVL的细分曲面的存储。     

Optimization and evaluation of shortest path queries

We investigate the problem of how to evaluate efficiently a collection of shortest path queries on massive graphs that are too big to fit in the main memory. To evaluate a shortest path query efficiently, we introduce two pruning algorithms. These algorithms differ on the extent of materialization of shortest path cost and on how the search space is pruned. By grouping shortest path queries properly, batch processing improves the performance of shortest path query evaluation. Extensive study is also done on fragment sizes, cache sizes and query types that we show that affect the performance of a disk-based shortest path algorithm. The performance and scalability of proposed techniques are evaluated with large road systems in the Eastern United States. To demonstrate that the proposed disk-based algorithms are viable, we show that their search times are significant better than that of main-memory Dijkstra's algorithm.     

Trading uninitialized space for time

The design of efficient graph algorithms usually precludes the test of edge existence, because an efficient support of that operation already requires time for the initialization of an adjacency-matrix representation. We describe an alternative representation of static directed graphs taking Θ(n+m) initialization time and using Θ(n²) space, which supports the efficient implementation of all usual operations on static graphs. The sparse graph representation allows the design of efficient graph algorithms using both iteration over all vertices adjacent with a given vertex and edge-existence operations, although at the expense of additional (uninitialized) space which may, nevertheless, be used for other purposes. To the best of our knowledge, the representation leads to the first graph algorithms with the disconcerting property that the time complexity is better than the space complexity.     

Spanners of bounded degree graphs

A k-spanner of a graph G is a spanning subgraph of G in which the distance between any pair of vertices is at most k times the distance in G. We prove that for fixed k,w, the problem of deciding if a given graph has a k-spanner of treewidth w is fixed-parameter tractable on graphs of bounded degree. In particular, this implies that finding a k-spanner that is a tree (a tree k-spanner) is fixed-parameter tractable on graphs of bounded degree. In contrast, we observe that if the graph has only one vertex of unbounded degree, then Treek-Spanner is NP-complete for k?4.     

基于单义域邻接图的圆弧与圆识别

工程图纸扫描输入与识别理解是ＣＡＤ推广和普及的关键步骤之一,主要解决已有大量图纸再利用问题。在工程图纸扫描图象识别研究中,圆弧识别是识别算法中的重点和难点。传统的圆弧识别多是基于线段逼近。该文提出一种基于单义域邻接图的圆弧及圆识别算法,可以直接提取圆弧,对二值图象作水平黑洲程编码,相关游程基于线宽与拓扑的一致性构成条形域,对其中多义域进行分裂得单义域（线段域和圆弧域）,单义域邻接图可较好描述图象的     

Self-stabilizing algorithms for efficient sets of graphs and trees

This paper presents distributed self-stabilizing algorithms to compute the efficiency of trees and optimally efficient sets of general graphs.     

Intractability of min- and max-cut in streaming graphs

We show that the exact computation of a minimum or a maximum cut of a given graph G is out of reach for any one-pass streaming algorithm, that is, for any algorithm that runs over the input stream of G's edges only once and has a working memory of o(n²) bits. This holds even if randomization is allowed.