O(n2.5) time algorithms for the subgraph homeomorphism problem on trees

The complexity of the subgraph homeomorphism problems have been open. We show O(n^2.5) time algorithms when the problems are restricted to trees, directed or undirected. The algorithm can be applied to the subtree isomorphism problem for unrooted trees with the same complexity, and improves over Reyner's O(n^3.5) algorithm for the subtree isomorphism problem.     

Faster Subtree Isomorphism

We study the subtree isomorphism problem: Given trees H and G, find a subtree of G which is isomorphic to H or decide that there is no such subtree. We give an O((k^1.5/log k)n)-time algorithm for this problem, where k and n are the number of vertices in H and G, respectively. This improves over the O(k^1.5n) algorithms of Chung and Matula. We also give a randomized (Las Vegas) O(k^1.376n)-time algorithm for the decision problem.     

Finding minimal spanning trees in a euclidean coordinate space

The minimal spanning tree problem of a point set in ak-dimensional Euclidean space is considered and a new version of the multifragmentMST-algorithm of Bentley and Friedman is given. The minimal spanning tree is found by repeatedly joining the minimal subtree with the closest subtree. Ak-d tree is used for choosing the connecting edges. Computation time of the algorithm depends on the configuration of the point set: for normally distributed random points the algorithm is very fast. Two extreme cases demandingO(n logn) andO(n ²) operations,n being the cardinality of the point set, are also given.     

A parallel algorithm for generating multiple ordering spanning trees in undirected weighted graphs

1.IntroductionLetG=(V,E,W)beaconnected,weightedandundirectedgraph,VeEE,w(e)(相似文献   

Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches

Let p≥2 be an integer and T be an edge-weighted tree. A cut on an edge of T is a splitting of the edge at some point on it. A p-edge-partition of T is a set of p subtrees induced by p−1 cuts. Given p and T, the max-min continuous tree edge-partition problem is to find a p-edge-partition that maximizes the length of the smallest subtree; and the min-max continuous tree edge-partition problem is to find a p-edge-partition that minimizes the length of the largest subtree. In this paper, O(n²)-time algorithms are proposed for these two problems, improving the previous upper bounds by a factor of log (min{p,n}). Along the way, we solve a problem, named the ratio search problem. Given a positive integer m, a (non-ordered) set B of n non-negative real numbers, a real valued non-increasing function F, and a real number t, the problem is to find the largest number z in {b/a|a∈[1,m],b∈B} such that F(z)≥t. We give an O(n+t_F×(logn+logm))-time algorithm for this problem, where t_F is the time required to evaluate the function value F(z) for any real number z.     

A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm

Recently, É. Tardos gave a strongly polynomial algorithm for the minimum-cost circulation problem and solved the open problem posed in 1972 by J. Edmonds and R.M. Karp. Her algorithm runs in O(m ² T(m, n) logm) time, wherem is the number of arcs,n is the number of vertices, andT(m, n) is the time required for solving a maximum flow problem in a network withm arcs andn vertices. In the present paper, taking an approach that is a dual of Tardos's, we also give a strongly polynomial algorithm for the minimum-cost circulation problem. Our algorithm runs in O(m ² S(m, n) logm) time and reduces the computational complexity, whereS(m, n) is the time required for solving a shortest path problem with a fixed origin in a network withm arcs,n vertices, and a nonnegative arc length function. The complexity is the same as that of Orlin's algorithm, recently developed by efficiently implementing the Edmonds-Karp scaling algorithm.     

Ordered priority queues

A new data structure called ordered priority queue is introduced in this paper. Elements stored in the data structure have a primary order (key) and a secondary order (priority) associated with them. An ordered min-priority queue allows users to find the minimum priority element in any range (according to key order) inO(logn) time. Such a data structure withn elements can be created inO(n logn) time usingO(n) storage. A specific implementation based on median split trees is presented. Sequential access of the elements can be done inO(n log logn) time andO(logn) extra storage.This work was supported in part by NASA under grant NAG 5-739.     

A note on optimal multiway split trees

Split trees are suitable data structures for storing records with different access frequencies. Under assumption that the access frequencies are all distinct, Huang has proposed anO(n ⁴ logm) time algorithm to construct an (m+1)-way split tree for a set ofn keys. In this paper, we generalize Huang's algorithm to deal with the case of non-distinct access frequencies. The technique used in the generalized algorithm is a generalization of Hesteret al.'s, where the binary case was considered. The generalized algorithm runs inO(n ⁵ logm) time.     

Inplace 2D matching in compressed images

The compressed matching problem is the problem of finding all occurrences of a pattern in a compressed text. In this paper we discuss the 2-dimensional compressed matching problem in Lempel–Ziv compressed images. Given a pattern P of (uncompressed) size m×m, and a text T of (uncompressed) size n×n, both in 2D-LZ compressed form, our algorithm finds all occurrences of P in T. The algorithm is strongly inplace, that is, the amount of extra space used is proportional to the best possible compression of a pattern of size m². The best compression that the 2D-LZ technique can obtain for a file of size m² is O(m). The time for performing the search is O(n²) and the preprocessing time is O(m³). Our algorithm is general in the sense that it can be used for any 2D compression which can be sequentially decompressed in small space.     

Efficient algorithms for finding minimum spanning trees in undirected and directed graphs

Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue). Their data structure, theFibonacci heap (or F-heap) supports arbitrary deletion inO(logn) amortized time and other heap operations inO(1) amortized time. In this paper we use F-heaps to obtain fast algorithms for finding minimum spanning trees in undirected and directed graphs. For an undirected graph containingn vertices andm edges, our minimum spanning tree algorithm runs inO(m logβ (m, n)) time, improved fromO(mβ(m, n)) time, whereβ(m, n)=min {i|log⁽ⁱ⁾ n ≦m/n}. Our minimum spanning tree algorithm for directed graphs runs inO(n logn + m) time, improved fromO(n log n +m log log log_(m/n+2) n). Both algorithms can be extended to allow a degree constraint at one vertex. Research supported in part by National Science Foundation Grant MCS-8302648. Research supported in part by National Science Foundation Grant MCS-8303139. Research supported in part by National Science Foundation Grant MCS-8300984 and a United States Army Research Office Program Fellowship, DAAG29-83-GO020.     

Encroaching lists as a measure of presortedness

Encroaching lists are a generalization of monotone sequences in permutations. Since ordered permutations contain fewer encroaching lists than random ones, the number of such listsm provides a measure of presortedness with advantages over others in the literature. Experimental and analytic results are presented to cast light on the properties of encroaching lists. Also, we describe a new sorting algorithm,melsort, with complexityO(nlogm). Thus it is linear for well ordered sets and reduces to mergesort andO(nlogn) in the worst case.This work was partially supported by National Science Foundation Grant CCSR-8714565.     

On the average number of nodes in a subtree of a tree

For any tree T (labelled, not rooted) of order n, it will be shown that the average number of nodes in a subtree of T is at least $\text{(n + 2)}\text{3}$, with this minimum achieved iff T is a path. For T rooted, the average number of nodes in a subtree containing the root is at least $\text{(n + 1)}\text{2}$ and always exceeds the average over all unrooted subtrees. For the maximum mean, examples show that there are arbitrarily large trees in which the average subtree contains essentially all of the nodes. The mean subtree order as a function on trees is also shown to be monotone with respect to inclusion.     

FFT-based algorithms for the string matching with mismatches problem

The string matching with mismatches problem requires finding the Hamming distance between a pattern P of length m and every length m substring of text T with length n. Fischer and Paterson's FFT-based algorithm solves the problem without error in O(σnlogm), where σ is the size of the alphabet Σ [SIAM–AMS Proc. 7 (1973) 113–125]. However, this in the worst case reduces to O(nmlogm). Atallah, Chyzak and Dumas used the idea of randomly mapping the letters of the alphabet to complex roots of unity to estimate the score vector in time O(nlogm) [Algorithmica 29 (2001) 468–486]. We show that the algorithm's score variance can be substantially lowered by using a bijective mapping, and specifically to zero in the case of binary and ternary alphabets. This result is extended via alphabet remappings to deterministically solve the string matching with mismatches problem with a constant factor of 2 improvement over Fischer–Paterson's method.     

Ray Shooting Amidst Convex Polygons in 2D

We consider the problem of ray shooting in a two-dimensional scene consisting ofmconvex polygons with a total ofnedges. We present a data structure that requiresO(mn log m) space and preprocessing time and that answers a ray shooting query inO(log² m log² n) time. If the polygons are pairwise disjoint, the space and preprocessing time can be improved toO((m²+n)log m) andO((m²+n log n)log m), respectively. Our algorithm also works for a collection of disjoint simple polygons. We also show that if we allow onlyO(n) space, a ray shooting query among a collection of disjoint simple polygons can be answered in timeO(m/[formula]¹⁺ log² n) time, for any >0.     

Tutte polynomials for trees

We define two two-variable polynomials for rooted trees and one two-variable polynomial for unrooted trees, all of which are based on the coranknullity formulation of the Tutte polynomial of a graph or matroid. For the rooted polynomials, we show that the polynomial completely determines the rooted tree, i.e., rooted trees T₁ and T₂ are isomorphic if and only if f(T₁) = f(T₂). The corresponding question is open in the unrooted case, although we can reconstruct the degree sequence, number of subtrees of size k for all k, and the number of paths of length k for all k from the (unrooted) polynomial. The key difference between these three polynomials and the standard Tutte polynomial is the rank function used; we use pruning and branching ranks to define the polynomials. We also give a subtree expansion of the polynomials and a deletion-contraction recursion they satisfy.     

Extended formulations for the cardinality constrained subtree of a tree problem

Given a tree with n nodes, we consider the problem of finding the most profitable subtree of that tree with at most K nodes which is known as the Cardinality Subtree of a Tree Problem. We present a new exact linear extended formulation with O(nK) two-indexed variables and O(nK) constraints.     

On separating two simple polygons by a single translation

LetP andQ be two disjoint simple polygons havingn sides each. We present an algorithm which determines whetherQ can be moved by a single translation to a position sufficiently far fromP, and which produces all such motions if they exist. The algorithm runs in timeO(t(n)) wheret(n) is the time needed to triangulate ann-sided polygon. Since Tarjan and Van Wyk have recently shown thatt(n)=O(n log logn) this improves the previous best result for this problem which wasO(n logn) even after triangulation.This research was supported by NSERC Grant A9293, FCAR Grant EQ-1678, and a Killam Fellowship from the Canada Council.     

A parallel search algorithm for directed acyclic graphs

A parallel algorithm for depth-first searching of a directed acyclic graph (DAG) on a shared memory model of a SIMD computer is proposed. The algorithm uses two parallel tree traversal algorithms, one for the preorder traversal and the other for therpostorder traversal of an ordered tree. Each of these traversal algorithms has a time complexity ofO(logn) whenO(n) processors are used,n being the number of vertices in the tree. The parallel depth-first search algorithm for a directed acyclic graphG withn vertices has a time complexity ofO((logn)²) whenO(n ^2.81/logn) processors are used.     

A Faster Deterministic Maximum Flow Algorithm

Cheriyan and Hagerup developed a randomized algorithm to compute the maximum flow in a graph with n nodes and m edges in O(mn + n² log²n) expected time. The randomization is used to efficiently play a certain combinatorial game that arises during the computation. We give a version of their algorithm where a general version of their game arises. Then we give a strategy for the game that yields a deterministic algorithm for computing the maximum flow in a directed graph with n nodes and m edges that runs in time O(mn(log_{m/n log n}n)). Our algorithm gives an O(mn) deterministic algorithm for all m/n = Ω(n^ε) for any positive constant ε, and is currently the fastest deterministic algorithm for computing maximum flow as long as m/n = ω(log n).     

Dynamic Text Indexing under String Updates

This paper generalizes the dynamic text indexing problem, introduced in [15], to insertion and deletion of strings. The problem is to quickly answer on-line queries about the occurrences of arbitrary pattern strings in a text that may change due to insertion or deletion of strings from it. To treat strings as atomic objects, we provide new sequential techniques and related data structures, which combine the suffix tree with the naming technique used in parallel computation on strings. We also introduce a geometric interpretation of the problem of finding the occurrences of a pattern in a given substring of the text. As a result, the algorithm allows the insertion in the text of a stringSinO(|S| log(n + |S|)) amortized time, and the deletion from the text of a stringSinO(|S| log n) amortized time, wherenis the length of the current text. A pattern search requiresO(p log p + upd ( + log p) + pocc) worst-case time, wherepis the length of the pattern andpoccis the number of its occurrences in the current text, obtained after the execution ofupdupdate operations. This solution requiresO(n² log n) space, which is not initialized.We also provide a technique to reduce the space toO(n log n), yielding a solution that requiresO((p + upd) log p + pocc) query time in the worst-case,O(|S| log^3/2(|S| + n)) amortized time to insert a stringSin, andO(|S| log^3/2n) amortized time to delete a stringSfrom the current text.Furthermore, we use our techniques to solve the novel on-line dynamic tree matching problem that requires the on-line detection of the occurrences of an arbitrary subtree in a forest of ordered labeled trees. The forest may change due to insertion or deletion of subtrees or by renaming of some nodes. Such a problem is solved by a simple reduction to the dynamic text indexing problem.