An Algorithm for Enumerating All Spanning Trees of a Directed Graph

We present an O(NV + V ³ ) time algorithm for enumerating all spanning trees of a directed graph. This improves the previous best known bound of O(NE + V+E) [1] when V ² =o(N) , which will be true for most graphs. Here, N refers to the number of spanning trees of a graph having V vertices and E edges. The algorithm is based on the technique of obtaining one spanning tree from another by a series of edge swaps. This result complements the result in the companion paper [3] which enumerates all spanning trees in an undirected graph in O(N+V+E) time. Received September 11, 1997; revised March 6, 1998.     

Listing all the minimum spanning trees in an undirected graph

Efficient polynomial time algorithms are well known for the minimum spanning tree problem. However, given an undirected graph with integer edge weights, minimum spanning trees may not be unique. In this article, we present an algorithm that lists all the minimum spanning trees included in the graph. The computational complexity of the algorithm is O(N(mn+n ² log n)) in time and O(m) in space, where n, m and N stand for the number of nodes, edges and minimum spanning trees, respectively. Next, we explore some properties of cut-sets, and based on these we construct an improved algorithm, which runs in O(N m log n) time and O(m) space. These algorithms are implemented in C language, and some numerical experiments are conducted for planar as well as complete graphs with random edge weights.     

Linear algorithm for lexicographic enumeration of CFG parse trees

We study CFG parse tree enumeration in this paper. By dividing the set of all parse trees into infinite hierarchies according to height of parse tree, the hierarchical lexicographic order on the set of parse trees is established. Then grammar-based algorithms for counting and enumerating CFG parse trees in this order are presented. To generate a parse tree of height n, the time complexity is O(n). If τ is a lowest parse tree for its yield, then O(n) =O(∥ gt ∥+ 1), where ∥τ ∥ is the length of the sentence (yield) generated by τ. The sentence can be obtained as a by-product of the parse tree. To compute sentence from its parse tree (needn’t be lowest one), the time complexity is O(node)+O(∥τ ∥ + 1), where node is the number of non-leaf nodes of parse tree τ. To generate both a complete lowest parse tree and its yield at the same time, the time complexity is O(∥τ ∥ + 1). Supported by the National Natural Science Foundation of China (Grant Nos. 60273023, 60721061)     

A VLSI Algorithm for Calculating the Tree to Tree Distance

Given two ordered, labeled trees β and α, to find the distance from tree β to tree α is an important problem in many fields, for example, the pattern recognition field. In this paper, a VLSI algorithm for calculating the tree to tree distance is presented. The computation structure of the algorithm is a 2-D Mesh with the sizem*n and the time isO(m+n), wherem,n are the numbers of nodes of the tree β and tree α, respectively.     

Finding the k Shortest Paths in Parallel

A concurrent-read exclusive-write PRAM algorithm is developed to find the k shortest paths between pairs of vertices in an edge-weighted directed graph. Repetitions of vertices along the paths are allowed. The algorithm computes an implicit representation of the k shortest paths to a given destination vertex from every vertex of a graph with n vertices and m edges, using O(m+nk log ² k) work and O( log^3k log ^*k+ log n( log log k+ log ^*n)) time, assuming that a shortest path tree rooted at the destination is pre-computed. The paths themselves can be extracted from the implicit representation in O( log k + log n) time, and O(n log n +L) work, where L is the total length of the output. Received July 2, 1997; revised June 18, 1998.     

Reconstructing a Minimum Spanning Tree after Deletion of Any Node

Abstract. Updating a minimum spanning tree (MST) is a basic problem for communication networks. In this paper we consider single node deletions in MSTs. Let G=(V,E) be an undirected graph with n nodes and m edges, and let T be the MST of G . For each node v in V , the node replacement for v is the minimum weight set of edges R(v) that connect the components of T-v . We present a sequential algorithm and a parallel algorithm that find R(v) for all V simultaneously. The sequential algorithm takes O(m log n) time, but only O(m α (m,n)) time when the edges of E are presorted by weight. The parallel algorithm takes O(log ² n) time using m processors on a CREW PRAM.     

Efficient associative algorithm to find the least spanning tree of a graph with a node degree constraint

Conclusion  We have described an associative algorithm to find the smallest spanning tree of a graph with a degree constraint on one of the nodes. The associative algorithm is based on Gabow's algorithm. It is described as a STAR procedure that runs in timeO(@#@ nlogn). This is also the time it takes to construct a minimum spanning tree of a graph on an associative parallel processor [4]. The associative algorithm relies on a number of new constructions that are also useful for other problems. Note that, unlike [13], we use a very simple and natural data representation on an associative parallel processor in the form of two-dimensional binary-coded tables. Translated from Kibernetika i Sistemnyi Analiz, No. 1., pp. 94–103, January–February, 1998.     

Efficient generation of plane trees

A rooted plane tree is a rooted tree with a left-to-right ordering specified for the children of each vertex. In this paper we give a simple algorithm to generate all rooted plane trees with at most n vertices. The algorithm uses O(n) space and generates such trees in O(1) time per tree without duplications. The algorithm does not output entire trees but the difference from the previous tree. By modifying the algorithm we can generate without duplications all rooted plane trees having exactly n vertices in O(1) time per tree, all rooted plane trees having at most n vertices with maximum degree at most D in O(1) time per tree, and all rooted plane trees having exactly n vertices including exactly c leaves in O(n−c) time per tree. Also we can generate without duplications all (non-rooted) plane trees having exactly n vertices in O(n³) time per tree.     

An O(log n) algorithm for parallel update of minimum spanning trees

Parallel algorithms are presented for updating a minimum spanning tree when the cost of an edge changes or when a new node is inserted in the underlying graph. Our model of computation is a parallel random access machine which allows simultaneous reads but prohibits simultaneous writes into the same memory location. The algorithms described in this paper for updating a minimum spanning tree require O(log n) time and O(n²) processors. These algorithms are efficient when compared to previously known algorithms for initial construction of a minimum spanning tree that require O(log²n) time and use O(n²) processors. The two main contributions of this paper are: (i) usage of an inverted tree for updating minimum spanning trees, and (ii) discovery of an interesting property of minimum spanning trees that we exploit to develop a novel algorithm for vertex insertion update.     

Constructing a minimum height elimination tree of a tree in linear time

Given a graph, finding an optimal vertex ranking and constructing a minimum height elimination tree are two related problems. However, an optimal vertex ranking does not by itself provide enough information to construct an elimination tree of minimum height. On the other hand, an optimal vertex ranking can readily be found directly from an elimination tree of minimum height. On n-vertex trees, the optimal vertex ranking problem already has a linear-time algorithm in the literature. However, there is no linear-time algorithm for the problem of finding a minimum height elimination tree. A naive algorithm for this problem requires O(nlogn) time. In this paper, we propose a linear-time algorithm for constructing a minimum height elimination tree of a tree.     

Improved heuristics for the bounded-diameter minimum spanning tree problem

Given an undirected, connected, weighted graph and a positive integer k, the bounded-diameter minimum spanning tree (BDMST) problem seeks a spanning tree of the graph with smallest weight, among all spanning trees of the graph, which contain no path with more than k edges. In general, this problem is NP-Hard for 4 ≤ k < n − 1, where n is the number of vertices in the graph. This work is an improvement over two existing greedy heuristics, called randomized greedy heuristic (RGH) and centre-based tree construction heuristic (CBTC), and a permutation-coded evolutionary algorithm for the BDMST problem. We have proposed two improvements in RGH/CBTC. The first improvement iteratively tries to modify the bounded-diameter spanning tree obtained by RGH/CBTC so as to reduce its cost, whereas the second improves the speed. We have modified the crossover and mutation operators and the decoder used in permutation-coded evolutionary algorithm so as to improve its performance. Computational results show the effectiveness of our approaches. Our approaches obtained better quality solutions in a much shorter time on all test problem instances considered.     

Polynomial Time Algorithms for 2-Edge-Connectivity Augmentation Problems

Abstract. Given a 2-edge-connected, real weighted graph G with n vertices and m edges, the 2-edge-connectivity augmentation problem is that of finding a minimum weight set of edges of G to be added to a spanning subgraph H of G to make it 2-edge-connected. While the general problem is NP-hard and 2 -approximable, in this paper we prove that it becomes polynomial time solvable if H is a depth-first search tree of G . More precisely, we provide an efficient algorithm for solving this special case which runs in O (M · α(M,n)) time, where α is the classic inverse of Ackermann's function and M=m · α(m,n) . This algorithm has two main consequences: first, it provides a faster 2 -approximation algorithm for the general 2 -edge-connectivity augmentation problem; second, it solves in O (m · α(m,n)) time the problem of restoring, by means of a minimum weight set of replacement edges, the 2 -edge-connectivity of a 2-edge-connected communication network undergoing a link failure.     

Combine and Conquer

We present a general technique for dynamizing a class of problems whose underlying structure is a computation graph embedded in a tree. We introduce three fully dynamic data structures, called path attribute systems, tree attribute systems, and linear attribute grammars, which extend and generalize the dynamic trees of Sleator and Tarjan. More specifically, we associate values, called attributes, with the nodes and paths of a rooted tree. Path attributes form a path attribute system if they can be maintained in constant time under path concatenation. Node attributes form a tree attribute system if the tree attributes of the tail of a path Π can be determined in constant time from the path attributes of Π. A linear attribute grammar is a tree-based linear expression such that the values of a node μ are calculated from the values at the parent, siblings, and&sol;for children of μ. We provide a framework for maintaining path attribute systems, tree attribute systems, and linear attribute grammars in a fully dynamic environment using linear space and logarithmic time per operation. Also, we demonstrate the applicability of our techniques by showing examples of graph and geometric problems that can be efficiently dynamized, including biconnectivity and triconnectivity queries, planarity testing, drawing trees and series-parallel digraphs, slicing floorplan compaction, point location, and many optimization problems on bounded tree-width graphs. Received May 13, 1994; revised October 12, 1995.     

Isomorphism for Graphs of Bounded Distance Width

In this paper we study the GRAPH ISOMORPHISM problem on graphs of bounded treewidth, bounded degree, or bounded bandwidth. GRAPH ISOMORPHISM can be solved in polynomial time for graphs of bounded treewidth, pathwidth, or bandwidth, but the exponent depends on the treewidth, pathwidth, or bandwidth. Thus, we look for special cases where ``fixed parameter tractable' polynomial time algorithms can be established. We introduce some new and natural graph parameters: the (rooted) path distance width, which is a restriction of bandwidth, and the (rooted) tree distance width, which is a restriction of treewidth. We give algorithms that solve GRAPH ISOMORPHISM in O(n ² ) time for graphs with bounded rooted path distance width, and in O(n ³ ) time for graphs with bounded rooted tree distance width. Additionally, we show that computing the path distance width of a graph is NP-hard, but both path and tree distance width can be computed in O(n ^k+1 ) time, when they are bounded by a constant k; the rooted path or tree distance width can be computed in O(ne) time. Finally, we study the relationships between the newly introduced parameters and other existing graph parameters. Received February 18, 1997; revised February 23, 1998.     

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.     

Deterministic Rendezvous in Graphs

Two mobile agents having distinct identifiers and located in nodes of an unknown anonymous connected graph, have to meet at some node of the graph. We seek fast deterministic algorithms for this rendezvous problem, under two scenarios: simultaneous startup, when both agents start executing the algorithm at the same time, and arbitrary startup, when starting times of the agents are arbitrarily decided by an adversary. The measure of performance of a rendezvous algorithm is its cost: for a given initial location of agents in a graph, this is the number of steps since the startup of the later agent until rendezvous is achieved. We first show that rendezvous can be completed at cost O(n + log l) on any n-node tree, where l is the smaller of the two identifiers, even with arbitrary startup. This complexity of the cost cannot be improved for some trees, even with simultaneous startup. Efficient rendezvous in trees relies on fast network exploration and cannot be used when the graph contains cycles. We further study the simplest such network, i.e., the ring. We prove that, with simultaneous startup, optimal cost of rendezvous on any ring is Θ(D log l), where D is the initial distance between agents. We also establish bounds on rendezvous cost in rings with arbitrary startup. For arbitrary connected graphs, our main contribution is a deterministic rendezvous algorithm with cost polynomial in n, τ and log l, where τ is the difference between startup times of the agents. We also show a lower bound Ω (n²) on the cost of rendezvous in some family of graphs. If simultaneous startup is assumed, we construct a generic rendezvous algorithm, working for all connected graphs, which is optimal for the class of graphs of bounded degree, if the initial distance between agents is bounded.     

Fixed Parameter Algorithms for DOMINATING SET and Related Problems on Planar Graphs

Abstract. We present an algorithm that constructively produces a solution to the k -DOMINATING SET problem for planar graphs in time O(c^ \sqrt k n) , where c=4^ 6\sqrt 34 . To obtain this result, we show that the treewidth of a planar graph with domination number γ (G) is O(\sqrt \rule 0pt 4pt \smash γ (G) ) , and that such a tree decomposition can be found in O(\sqrt \rule 0pt 4pt \smash γ (G) n) time. The same technique can be used to show that the k -FACE COVER problem (find a size k set of faces that cover all vertices of a given plane graph) can be solved in O(c ₁ ^ \sqrt k n) time, where c ₁ =3^ 36\sqrt 34 and k is the size of the face cover set. Similar results can be obtained in the planar case for some variants of k -DOMINATING SET, e.g., k -INDEPENDENT DOMINATING SET and k -WEIGHTED DOMINATING SET.     

A Randomized Linear-Work EREW PRAM Algorithm to Find a Minimum Spanning Forest

We present a randomized EREW PRAM algorithm to find a minimum spanning forest in a weighted undirected graph. On an n -vertex graph the algorithm runs in o(( log n) ^{1+ ɛ} ) expected time for any ɛ >0 and performs linear expected work. This is the first linear-work, polylog-time algorithm on the EREW PRAM for this problem. This also gives parallel algorithms that perform expected linear work on two general-purpose models of parallel computation—the QSM and the BSP.     

Spanning-tree based coverage of continuous areas by a mobile robot

This paper considers the problem of covering a continuous planar area by a square-shaped tool attached to a mobile robot. Using a tool-based approximation of the work-area, we present an algorithm that covers every point of the approximate area for tasks such as floor cleaning, lawn mowing, and field demining. The algorithm, called Spanning Tree Covering (STC), subdivides the work-area into disjoint cells corresponding to the square-shaped tool, then follows a spanning tree of the graph induced by the cells, while covering every point precisely once. We present and analyze three versions of the STC algorithm. The first version is off-line, where the robot has perfect apriori knowledge of its environment. The off-line STC algorithm computes an optimal covering path in linear time O(N), where N is the number of cells comprising the approximate area. The second version of STC is on-line, where the robot uses its sensors to detect obstacles and construct a spanning tree of the environment while covering the work-area. The on-line STC algorithm completes an optimal covering path in time O(N), but requires O(N) memory for its implementation. The third version of STC is “ant”-like. In this version, too, the robot has no apriori knowledge of the environment, but it may leave pheromone-like markers during the coverage process. The ant-like STC algorithm runs in time O(N), and requires only O(1) memory. Finally we present simulation results of the three STC algorithms, demonstrating their effectiveness in cases where the tool size is significantly smaller than the work-area characteristic dimension. This revised version was published online in August 2006 with corrections to the Cover Date.     

Satisfiability, Branch-Width and Tseitin tautologies

For a CNF τ, let w _b (τ) be the branch-width of its underlying hypergraph, that is the smallest w for which the clauses of τ can be arranged in the form of leaves of a rooted binary tree in such a way that for every vertex its descendants and non-descendants have at most w variables in common. In this paper we design an algorithm for solving SAT in time n^O(1)2^O(w_b(t)){n^{O(1)}2^{O(w_b(\tau))}}. This in particular implies a polynomial algorithm for testing satisfiability on instances with branch-width O(log n). Our algorithm is a modification of the width based automated theorem prover (WBATP) which is a popular (at least on the theoretical level) heuristic for finding resolution refutations of unsatisfiable CNFs, and we call it Branch-Width Based Automated Theorem Prover (BWBATP). As opposed to WBATP, our algorithm always produces regular refutations. Perhaps more importantly, its running time is bounded in terms of a clean combinatorial characteristic that can be efficiently approximated, and that the algorithm also produces, within the same time, a satisfying assignment if τ happens to be satisfiable.