Given a set of data graphs and a query graph, graph isomorphism query processing is the problem of finding all the data graphs that are isomorphic to the query graph. Graph isomorphism query processing is a core problem in graph analysis of various application domains. In existing approaches, index construction or query processing takes much time as the graph sizes increase. In this paper, we propose an efficient algorithm for graph isomorphism query processing. We introduce the color-label distribution which represents the canonical coloring of a vertex-labeled graph. Based on degree sequences and color-label distributions, we introduce a two-level index, which helps us efficiently solve graph isomorphism query processing. Experimental results on real datasets show that the proposed algorithm is orders of magnitude faster than the state-of-the-art algorithms in terms of index construction time, and it runs faster than existing algorithms in terms of query processing time as the graph sizes increase.

Graph isomorphism is a core problem in graph analysis of various application domains. Given two graphs, the graph isomorphism problem is to determine whether there exists an isomorphism between them. As real-world graphs are getting bigger and bigger, applications demand practically fast algorithms that can run on large-scale graphs. However, existing approaches such as graph canonization and subgraph isomorphism show limited performances on large-scale graphs either in time or space. In this paper, we propose a new approach to graph isomorphism, which is the framework of pairwise color refinement and efficient backtracking. The main features of our approach are: (1) pairwise color refinement and binary cell mapping (2) compressed CS (candidate space), and (3) partial failing set, which together lead to a much faster and scalable algorithm for graph isomorphism. Extensive experiments with real-world datasets show that our approach outperforms state-of-the-art algorithms by up to orders of magnitude in terms of running time.

This article presents a real-time randomized streaming string-matching algorithm that uses O (log m ) space. The algorithm only makes one-sided small probability false-positive errors, possibly reporting phantom occurrences of the pattern, but never missing an actual occurrence.

We study three-dimensional periodicity in finite arrays and introduce four categories of three-dimensional periodicity: edge-periodic, side-aperiodic, side-periodic, and completely periodic. We analyze three-dimensional periodicity thoroughly, and we characterize periods of a finite three-dimensional array by a small number of vectors. This periodicity analysis leads to an efficient algorithm for three-dimensional pattern matching.

We prove general lower bounds for set recognition on random access machines (RAMs) that operate on real numbers with algebraic operations $\{+,-,\times,/\}$, as well as RAMs that use the operations $\{+,-,\times,\lfloor\;\rfloor\}$. We do it by extending a technique formerly used with respect to algebraic computation trees. In the case of algebraic computation trees, the complexity was related to the number of connected components of the set W to be recognized. For RAMs, four similar results apply to the number of connected components of $W^\circ$, the topological interior of W. Two results use $(\overline W)^\circ$, the interior of the topological closure of W. We present theorems that can be applied to a variety of problems and obtain lower bounds, many of them tight, for the following models: 1. A RAM which operates on real numbers, using integers to address memory and either the operations $\{+,-,\times,/\}$ or $\{+,-,\times,\lfloor\;\rfloor\}$. 2. A RAM of each of the above instruction sets, extended by allowing arbitrary real numbers to be used as memory addresses and adding a test-for-integer instruction. 3. A RAM of each of the above instruction sets which can compute with arbitrary real numbers, as well as use them for memory addressing, while the input is restricted to the integers. (For one result on this model, we require that all program constants be rational.)

We initiate a graph-theoretic study of privacy in distributed environments with mobile eavesdroppers ("bugs"). For two privacy tasks—distributed database maintenance and message transmission—a computationally unbounded adversary “plays an eavesdrpping game,” coordinating the moment of the bugs among the sites to learn the current memory contents. Many different adversaries are considered, motivated by differences in eavesdropping technologies. We characterize the feasibility of the two privacy tasks combinatorially, construct protocols for the feasible cases, and analyze their computational complexity.

This paper introduces compressed certificates for planarity, biconnectivity and triconnectivity in planar graphs, and proves many structural properties of certificates in planar graphs. As an application of our compressed certificates, we develop efficient dynamic planar algorithms. In particular, we consider the following three operations on a planar graph G : (i) insert an edge if the resultant graph remains planar; (ii) delete an edge; and (iii) test whether an edge could be added to the graph without violating planarity. We show how to support each of the above operations in O ( n 2/3 ) time, where n is the number of vertices in the graph. The bound for tests and deletions is worst-case, while the bound for insertions is amortized. This is the first algorithm for this problem with sub-linear running time, and it affirmatively answers a question posed in Epstein et al. [1992]. We use our compressed certificates for biconnectivity and triconnectivity to maintain the biconnected and triconnected components of a dynamic planar graph. The time bounds are the same: O ( n 2/3 ) worst-case time per edge deletion, O ( n 2/3 ) amortized time per edge insertion, and O ( n 2/3 ) amortized time per edge insertion, and O ( n 2/3 )worst-case time to check whether two vertices are either biconnected or triconnected.

We consider the problem of maintaining a dynamic planar graph subject to edge insertions and edge deletions that preserve planarity but that can change the embedding. We describe algorithms and data structures for maintaining information about 2- and 3-vertex-connectivity, and 3- and 4-edge-connectivity in a planar graph in O(n 1/2 ) amortized time per insertion, deletion, or connectivity query. All of the data structures handle insertions that keep the graph planar without regard to any particular embedding of the graph. Our algorithms are based on a new type of sparsification combined with several properties of separators in planar graphs.

We present a parallel algorithm on a CRCW PRAM for three-dimensional pattern matching, i.e., finding all occurrences of a pattern of size TTZ3 in a text of size n3.The text search of the algorithm is alphabet-independent and runs in optimal constant time.The preprocessing computes a witness array for the pattern, and it runs in O(log m) time using rn3 processors.The witness computation uses multilayer suf%x trees and it works for any dimensions.Our result is based on a new characterization of three-dimensional periodicity.The parallel algorithm can be translated into a sequential algorithm for three-dimensional pattern match-ing whose text search is alphabet-independent and runs in 0(n3 ) time and whose preprocessing runs in 0(m3 log a) time, where u = min(l Xl, m3) and X is the alphabet of symbols.

We provide data strutures that maintain a graph as edges are inserted and deleted, and keep track of the following properties with the following times: minimum spanning forests, graph connectivity, graph 2-edge connectivity, and bipartiteness in time O ( n 1/2 ) per change; 3-edge connectivity, in time O ( n 2/3 ) per change; 4-edge connectivity, in time O ( n α( n )) per change; k -edge connectivity for constant k , in time O ( n log n ) per change;2-vertex connectivity, and 3-vertex connectivity, in the O ( n ) per change; and 4-vertex connectivity, in time O ( n α( n )) per change. Further results speed up the insertion times to match the bounds of known partially dynamic algorithms. All our algorithms are based on a new technique that transforms an algorithm for sparse graphs into one that will work on any graph, which we call sparsification.

The authors have solved the all pairs shortest distances (APSD) problem for graphs with integer edge lengths. Our algorithm is subcubic for edge lengths of small (⩽M) absolute value. In this paper we show how to transform these algorithms to solve the all pairs shortest paths (APSP), in the same time complexity, up to a polylogarithmic factor. Forn=|V| the number of vertices,Mthe bound on edge length, andωthe exponent of matrix multiplication, we get the following results: 1. A directed nonnegative APSP(n, M) algorithm which runs inÕ(T(n, M)) time, where T(n, m)=\big\{\begin{align}M^{\omega -1)/2} n^{3+\omega )/2}, & 1\le M\le n^{3-\omega )/(\omega +1)}\\ Mn^{5\omega -3)/(\omega +1)}, & n^{(3-\omega )/(\omega +1)}\le M\le n^2(3-\omega )/(\omega +1)}.\end{align} 2. An undirected APSP(n, M) algorithm which runs inÕ(M(ω+1)/2nω log(Mn)) time. 3. A general APSP(n, M) algorithm which runs inÕ((Mn)(3+ω)/2).

Given a pattern string of length m for the string-matching problem, we design an algorithm that computes deterministic samples of a sufficiently long substring of the pattern in constant time. This problem used to be the bottleneck in the pattern preprocessing for one- and two-dimensional pattern matching. The best previous time bound was O(log 2 m / log log m). We use this algorithm to obtain the following results (all algorithms below are optimal parallel algorithms on a CRCW PRAM): a deterministic string-matching algorithm which takes O(log log m) time for preprocessing and constant time for text search, which are the best possible in both preprocessing and text search; a constant-time deterministic string-matching algorithm in the case where the text length n satisfies $n=\Omega(m^{1+\epsilon})$ for a constant $\epsilon > 0$; a simple string-matching algorithm that has constant time with high probability for random input; the main result: a constant-expected-time Las Vegas algorithm for computing the period of the pattern and all witnesses and thus for string matching itself; in both cases, an $\Omega(\log\log m)$ lower bound is known for deterministic algorithms.

We describe algorithms and data structures for maintaining a dynamic planar graph subject to edge insertions and edge deletions that preserve planarity but that can change the embedding. We give a fully dynamic planarity testing algorithm that maintains a graph subject to edge insertions and deletions and that allows queries that test whether the graph is currently planar, or whether a potential new edge would violate planarity, inO(n1/2) amortized time per update or query. We give fully dynamic algorithms for maintaining the connected components, the best swap and the minimum spanning forest of a planar graph inO(log n) worst-case time per insertion andO(log2 n) per deletion. Finally, we give fully dynamic algorithms for maintaining the 2-edge-connected components of a planar graph inO(log n) amortized time per insertion andO(log2 n) per deletion. All of the data structures, except for the one that answers planarity queries, handle only insertions that keep the graph planar. All our algorithms improve previous bounds. The improvements are based upon a new type of sparsification combined with several properties of separators in planar graphs.

We study two-dimensional periodicity, introduced by Amir and Benson. We characterize periods of a two-dimensional array, namely, the vectors such that two copies of the array, one shifted by the vector over the other, overlap without a mismatch. Using this characterization, we design an alphabet-independent linear-time algorithm for two-dimensional witness computation, i.e., an $O(m^2 )$-time algorithm that finds periods of an $m \times m$ array as well as witnesses against nonperiods of the array among the vectors whose length is less than ${m / 4}$. The constant in the O notation does not depend on the alphabet size. Combined with the alphabet-independent text-processing algorithm of Amir, Benson, and Farach [SIAM J. Comput., 23 (1994), pp. 313–323], this leads to the first alphabet-independent linear-time algorithm for two-dimensional pattern matching.

Byzantine Agreement among processors is a basic primitive in distributed computing. It comes in a number of basic fault models: "Crash", "Omission" and "Malicious" adversarial behaviors. The message complexity of the primitive has been known for the strong failure models of Malicious and Omission adversary since the early 80's, while the question for the more benign Crash failure model has been open. We show how to solve agreement in the presence of crash failures using O(n) messages which is optimal, thus settling a thirteen year old open problem. Our solution has almost linear time and our new algorithmic techniques have further implications: a family of "early stopping" agreement protocols with improved message-complexity; and a new solution to "Checkpoint" yielding a substantial improvement of the protocol for distributed work performance under adaptive parallelism in a network of workstations.

A parallel algorithm is work-optimal if it uses the srrlallest possible work; a work-optimal algorithm is worktirne-optimal if it also uses the smallest possible time.We design worl{-time-optirnal algorithm for a number of string processing problems on the EREW-PRAM and the hypercuhe, They include string matching and two dimensional pattern matching.No such algorithms have been known before for any of these probl~ms.

This paper examines the power of the shift primitive when included in a high level model operatin on unbounded integers. It is shown that in such a model a constant number of registers suffices for simulating an unbounded memory RAM of the sam instruction set. The simulation is on-line, and its cost can be bounded by O(tα(s)), for a RAM program of running time t and space s. By multitask programming (postponing lengthy updates) it can be made close to real-time (O(α(s)) per operation).

Given a pattern string, we describe a way to preprocess it. We design a CRCW-PRAM constant time optimal parallel algorithm for finding all occurrences of the (preprocessed) pattern in any given text.

This paper presents two efficient concurrent-read concurrent-write parallel algorithms that find all palindromes in a given string: 1. An O(log n) time, n-processor algorithm over general alphabets. In the case of constant size alphabets the algorithm requires only nlog n processors, and thus achieves an optimalspeedup. 2. An O(log log n) time, n log nloglog n-processor algorithm over general alphabets. This is the fastest possible time with the number of processors used. These new results improve on the known parallel palindrome detection algorithms by using smaller auxiliary space and either by making fewer operations or by achieving a faster running time.

Recently, R. Kosaraju gave an O(nm('7' polylog(m )) step algorithm for tree pattern matching.We Improve this result by designing a simple 0( nfipolylog( m)) algorithm, Categories and Suhjcct Descriptors: F.

We study the parallel computation of dynamic programming. We consider four important dynamic programming problems which have wide application, and that have been studied extensively in sequential computation: (1) the 1D problem, (2) the gap problem, (3) the parenthesis problem, and (4) the RNA problem. The parenthesis problem has fast parallel algorithms; almost no work has been done for parallelizing the other three. We present a unifying framework for the parallel computation of dynamic programming recurrences with more than O(1) dependency. We use two well-known methods, the closure method and the matrix product method, as general paradigms for developing parallel algorithms. Combined with various techniques, they lead to a number of new results. Our main results are optimal sublinear-time algorithms for the 1D, parenthesis, and RNA problems.

We define two conditions on a random access machine (RAM) with arithmetic and Boolean instructions and possible bounds on word and memory sizes. One condition asserts that we either restrict attention to short words or allow non-uniform programs. The second asserts that we either allow a large memory or a double-precision multiplication. Our main theorem shows that the RAM can sort in o(nlog n) time if and only if both of these conditions hold. This theorem breaks down into four upper bounds only one of which has been known before, and two lower bounds neither of which has been known.>

All algorithms below are optimal alphabet-independent parallel CRCW PRAM algorithms. In one dimension: Given a pattern string of length m for the string-matching problem, we design an algorithm that computes a deterministic sample of a sufficiently long substring in constant time. This problem used to be a bottleneck in the pattern preprocessing for one- and two-dimensional pattern matching. The best previous time bound was O(log/sup 2/ m/log log m). We use this algorithm to obtain the following results. 1. Improving the preprocessing of the constant-time text search algorithm from O(log/sup 2/ m/log log m) to n(log log m), which is now best possible. 2. A constant-time deterministic string-matching algorithm in the case that the text length n satisfies n=/spl Omega/(m/sup 1+/spl epsiv//) for a constant /spl epsiv/>0. 3. A simple probabilistic string-matching algorithm that has constant time with high probability for random input. 4. A constant expected time Las-Vegas algorithm for computing the period of the pattern and all witnesses and thus string matching itself, solving the main open problem remaining in string matching.>

We initiate a graph-theoretic approach to study the (information-theoretic) maintenance of privacy in distributed environments in the presence of a bounded number of mobile eavesdroppers ("bugs"). For two fundamental privacy problems-secure message transmission and distributed database maintenance-we assume an adversary is "playing eavesdropping games," coordinating the movement of the bugs among the sites to learn the current memory contents. We consider various mobility settings (adversaries), motivated by the capabilities (strength) of the bugging technologies (e.g., how fast can a bug be reassigned). We combinatorially characterize and compare privacy maintenance problems, determine their feasibility (under numerous bug models), suggest protocols for the feasible cases, and analyze their computational complexity.>

Article Free Access Share on Separator based sparsification for dynamic planar graph algorithms Authors: David Eppstein View Profile , Zvi Galil View Profile , Giuseppe F. Italiano View Profile , Thomas H. Spencer View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 208–217https://doi.org/10.1145/167088.167159Published:01 June 1993Publication History 23citation582DownloadsMetricsTotal Citations23Total Downloads582Last 12 Months25Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The problem of maintaining the 3-edge-connected components of a graph undergoing repeated dynamic modifications, such as edge and vertex insertions, is studied. This paper shows how to answer the question of whether or not two vertices belong to the same 3-edge-connected component of a connected graph that is undergoing only edge insertions. Any sequence of q query and updates on an n-vertex graph can be performed in $O((n + q)\alpha (q,n))$ time.

The subcubic (O(n/sup w/) for w(3) algorithms to multiply Boolean matrices do not provide the witnesses; namely, they compute C=A.B but if C/sub ij/=1 they do not find an index k (a witness) such that A/sub ik/=B/sub kj/=1. The authors design a deterministic algorithm for computing the matrix of witnesses that runs in O(n/sup w/) time, where here O(n/sup w/) denotes O(n/sup w/(log n)/sup O(1)/). The subcubic methods to compute the shortest distances between all pairs of vertices also do not provide for witnesses; namely they compute the shortest distances but do not generate information for computing quickly the paths themselves. A witness for a shortest path from v/sub i/ to v/sub j/ is an index k such that v/sub k/ is the first vertex on such a path. They describe subcubic methods to compute such witnesses for several versions of the all pairs shortest paths problem. As a result, they derive shortest paths algorithms that provide characterization of the shortest paths in addition to the shortest distances in the same time (up to a polylogarithmic factor) needed for computing the distances; namely O(n/sup (3+w)/2/) time in the directed case and O(n/sup w/) time in the undirected case. They also design an algorithm that computes witnesses for the transitive closure in the same time needed to compute witnesses for Boolean matrix multiplication.>

The authors provide data structures that maintain a graph as edges are inserted and deleted, and keep track of the following properties: minimum spanning forests, best swap, graph connectivity, and graph 2-edge-connectivity, in time O(n/sup 1/2/log(m/n)) per change; 3-edge-connectivity, in time O(n/sup 2/3/) per change; 4-edge-connectivity, in time O(n alpha (n)) per change; k-edge-connectivity, in time O(n log n) per change; bipartiteness, 2-vertex-connectivity, and 3-vertex-connectivity, in time O(n log(m/n)) per change; and 4-vertex-connectivity, in time O(n log(m/n)+n alpha (n)) per change. Further results speed up the insertion times to match the bounds of known partially dynamic algorithms. The algorithms are based on a technique that transforms algorithms for sparse graphs into ones that work on any graph, which they call sparsification.>

A. Amir, G. Benson and M. Farach (see Proc. 24th STOC, p.59-68 (1992)) gave an algorithm for two-dimensional pattern matching (ABF for short) whose text processing is independent of the alphabet and takes O(n/sup 2/) time, but whose pattern processing is dependent on the alphabet and takes O(m/sup 2/log mod Sigma mod ) time. The authors present an algorithm that is truly independent of the alphabet and takes linear O(m/sup 2/+n/sup 2/) time. As in the Knuth-Morris-Pratt algorithm, the only operation on the alphabet is the equality test of two symbols. All previous algorithms except the ABF algorithm reduce the two-dimensional problem into one-dimensional string matching, and use known techniques in string matching. The ABF algorithm uses two-dimensional periodicity for text processing, but their pattern processing resorts to one-dimensional techniques. The authors present a two-dimensional technique for both pattern processing and text processing.>

Given a pattern string, we describe a way to preprocess it. We design a constant-time optimal parallel algorithm for finding all occurences of the (preprocessed) pattern in any given text.

The fully dynamic planarity testing problem consists of performing an arbitrary sequence of the following three kinds of operations on a planar graph G (i) insert an edge if the i resultant graph remains planar; (ii delete an edge; and (iii) test whether an edge could be ad ed to the graph without violating planarity.We show how to support each of the above operations in 0(TZ2/3 ) time, where n is the number of vertices in the graph.The bound for tests and deletions is worst-case, while the bound for insertions is amortized.This is the first algorithm for this problem with sub-linear running time.The same data structure haa further applications in maintaining the biconnected and triconnected components of a dynamic planar graph.

What is the cost of random access to memory?This fundamental problem M addressed by studying the simulation of random addressing by a machine that lacks it, a "pointer machine.'"The problem is formulated in the context of high-level computational models, allowing the use of a data type of our choice, A RAM program of time tand space s can be simulated m 0( f log .s)time using a tree.To enable a lower-bound proof, we formalize a notion of incompressibility for general data types.The main theorem states that for all incompressible data types an Ll( f log s) lower bound holds.Incompressibility trivially holds for strings, but is harder to prove for a powerful data type.Incompressibility is proved for the real numbers with a set of primitives that includes all functions that are continuous except on a countable closed set.This may be the richest set of operations considered m a lower-bound proof.It is also shown that the integers with arithmetic +, -, x and [ .x/2~,any Boolean operations, and left shift are incompressible.Tbe situation is reversed once right shift is allowed.

Dynamic programming solutions to a number of different recurrence equations for sequence comparison and for RNA secondary structure prediction are considered. These recurrences are defined over a number of points that is quadratic in the input size; however only a sparse set matters for the result. Efficient algorithms for these problems are given, when the weight functions used in the recurrences are taken to be linear. The time complexity of the algorithms depends almost linearly on the number of points that need to be considered; when the problems are sparse this results in a substantial speed-up over known algorithms.

Dynamic programming solutions to two recurrence equations, used to compute a sequence alignment from a set of matching fragments between two strings, and to predict RNA secondary structure, are considered. These recurrences are defined over a number of points that is quadratic in the input size; however, only a sparse set matters for the result. Efficient algorithms are given for solving these problems, when the cost of a gap in the alignment or a loop in the secondary structure is taken as a convex or concave function of the gap or loop length. The time complexity of our algorithms depends almost linearly on the number of points that need to be considered; when the problems are sparse, this results in a substantial speed-up over known algorithms.

This paper presents an $\Omega (\log \log m)$ lower bound on the number of rounds necessary for finding occurrences of a pattern string $P[1..m]$ in a text string $T[1..2m]$ in parallel using m comparisons in each round. The bound is within a constant factor of the fastest algorithm for this problem [D. Breslauer and Z. Galil, SIAM J. Comput.,19 (1990), pp. 1051–1058] and also holds for an m-processor CRCW-PRAM in the case of a general alphabet. Consequently, the paper derives the parallel complexity of the string matching problem using p processors for general alphabets, which is • $\Theta ( \frac{m}{p} )$ if $p \leq \frac{m}{{\log \log m}}$, • $\Theta (\log \log m)$ if $\frac{m}{{\log \log m}} \leq p \leq m$, • $\Theta (\log \log _{2p/m} p)$ if $m \leq p \leq m^2 $, • $\Theta (1)$ if $p \geq m^2 $, or in short $\Theta \lceil \frac{m}{p} \rceil + \log \log _{\lceil 1 + p/m \rceil } 2p)$.

It is shown that, for any pattern of length m and for any text of length n, it is possible to find all occurrences of the pattern in the text in overall linear time and at most $\frac{4}{3}n - \frac{1}{3}m$ character comparisons. In fact, the bound on the number of character comparisons is usually tighter than this, for the bound is expressed in terms of the structure of the pattern. The algorithm here need not have any knowledge of the alphabet. This improves the best previous bound of $1.5n-.5(m - 1)$ obtained by Colussi [Inform. and Comput., to appear] and Apostolico and Crochemore [Tech. Report TR89-75, LITP, Université de Paris, Paris, France, 1989]. In a companion paper [SIAM J. Comput., 20 (1991), pp. 1008–1020], the authors show a lower bound for on-line algorithms that is equal to $\frac{4}{3}n - \frac{1}{3}m$ for $m = 3$. For $m = 1,2,n$ character comparisons is optimal. This algorithm is based on a new analysis of the string matching algorithm by Colussi. Moreover, this new analysis of Colussi’s algorithm confirms the experimental results showing that his algorithm performs very well in practice [Inform. and Comput., to appear].

This paper studies the problem of maintaining the 2-edge-connected components of a graph undergoing repeated dynamic modifications, such as edge insertions and edge deletions. It is shown how to test at any time whether two vertices belong to the same 2-edge-connected component, and how to insert and delete an edge in $O(m^{2/3} )$ time in the worst case, where m is the current number of edges in the graph. This answers a question posed by Westbrook and Tarjan [Tech. Report CS-TR-229-89, Dept. of Computer Science, Princeton University, Princeton, NJ, August 1989; Algorithmica., to appear]. For planar graphs, the paper presents algorithms that support all these operations in $O(\sqrt {n\log \log n} )$ worst-case time each, where n is the total number of vertices in the graph.

Dynamic programming is a general problem-solving technique that has been widely used in various fields such as control theory, operations research, biology and computer science. In many applications dynamic programming problems satisfy additional conditions of convexity, concavity and sparsity. This paper presents a classification of dynamic programming problems and surveys efficient algorithms based on the three conditions.

A technique is described for deriving lower bounds and tradeoffs for data structure problems. Two quantities are defined. The output variability depends only on the model of computation. It characterizes in some sense the power of a model. The problem variability depends only on the problem under consideration. It characterizes in some sense the difficulty of the problem. The first theorem states that if a model's output variability is smaller than the problem variability, a lower bound on the worst case (average case) time for the problem follows. A RAM that can add, subtract and compare unbounded integers is considered. The second theorem gives an upper bound on the output variability of this model. The two theorems are used to derive lower bounds for the union-find problem in this RAM.>

This talk presents the derivation of an\\Omega\\Gamma/28 log m) lower bound on the number of rounds necessary for finding occurrences of a pattern string P [1::m] in a text string T [1::2m] in parallel using m comparisons in each round. The parallel complexity of the string matching problem using p processors for general alphabets follows. 1. Introduction Better and better parallel algorithms have been designed for string-matching. All are on CRCW-PRAM with the weakest form of simultaneous write conflict resolution: all processors which write into the same memory location must write the same value of 1. The best CREW-PRAM algorithms are those obtained from the CRCW algorithms for a logarithmic loss of efficiency. Optimal algorithms have been designed: O(logm) time in [8, 17] and O(log log m) time in [4]. (An optimal algorithm is one with pt = O(n) where t is the time and p is the number of processors used.) Recently, Vishkin [18] developed an optimal O(log m) time algorithm. Unlike...

We consider the problem of maintaining the 2-edgeconnected and the 3-edge-connected compoueutti of a graph undergoing repeated dynamic modifications, such as edgeinsertions and edgedeletions.We show how to test at any time whether two vertices belong to the same 2-edge-connected component, and how to insert and delete an edge in 0(m213) time in the worst case, where m is the current number of edges in the graph.This answers a question posed by Westbrook and Tarjan [18].For planar graphs, we present algorithms that support all these operations in O(~n- ) worst-case time each, where n is the total number of vertices in the graph.Finally, we show how to answer whether two vertices belong to the same 3-edge-connected component of a connected graph that is undergoing only edge insertions, Any sequence of q query and updates on an n-vertex graph can be performed in O((n + q)a(q, n)) time.1. Introduction Given an undirected graph G = (V, E), and au integer k ~2, a pair of vertices (u, v) is said to be kedge-connected if the removal of any k -1 edges in G leaves u and v connected.The vertices c,f a graph G are partitioned by this relationship into ecluivalence classes called k-edge-connected components.A graph is said to be k-edge-connected if all its pairs of vertices are k-edge-connected.A brsdge is an edge whose removal "Work partially supported by

Abstract We consider a variant of the set union problem, called set union with arbitrary deunions, that consists of maintaining a collection of disjoint sets under three kinds of operations: union, find, and deunion(i). A deunion(i) undoes the ith union performed so far and not yet undone. Each operation can be supported in O(log n) time in the worst-case, where n is the total number of items in the collection of disjoint sets. Motivations for this problem arise in logic programming memory management.

This paper provides several lower bounds on the number of character comparisons that any string matching algorithm must perform in the worst case in order to find occurrences of a pattern string in a text string. The class of algorithms that are considered need not know the alphabet.

This paper describes a new approach for solving the subset-sum problem. It is useful for solving other NP-hard problems. The limits and potential of this approach are discussed. The approach yields an algorithm for solving the dense version of the subset-sum problem. It runs in time $O(\ell \log \ell )$, where $\ell $ is the bound on the size of the elements. But for dense enough inputs and target numbers near the middle sum, it runs in time $O(m)$, where m is the number of elements. Consequently, it improves the previously best algorithms by at least one order of magnitude and sometimes by two. The algorithm yields a characterization of the set of subset sums as a collection of arithmetic progressions with the same difference. This characterization is derived by elementary number-theoretic and algorithmic techniques. Such a characterization was first obtained by using analytic number theory and yielded inferior algorithms.

The maximal number of character comparisons made by a linear-time string matching algorithm, given a text string of length n and a pattern string of length m over a general alphabet, is investigated. The number is denoted by c(n,m) or approximated by (1+C)n, where C is a universal constant. The subscript 'online' is added when attention is restricted to online algorithms, and the superscript '1' is added when algorithms that find only one occurrence of the pattern in the text are considered. It is well known that n>

Recently, R. Kosaraju (Proc. 30th IEEE Symp. on Foundations of Computer Science, 1989, p.178-83) gave an O(nm/sup 0.75/ polylog(m))-step algorithm for tree pattern matching. The authors improve this result by designing a simple O(n square root m polylog (m)) algorithm.>

The least weight subsequence problem is a special case of the one-dimensional dynamic programming problem where D[i] = E[i]. The modified edit distance problem, which arises in molecular biology. geology, and speech recognition, can be decomposed into 2n copies of the problem.

An optimal $O(\log \log n)$ time parallel algorithm for string matching on CROW-PRAM is presented. It improves previous results of Galil [Inform, and Control, 67 (1985), pp. 144–157] and Vishkin [Inform, and Control, 67 (1985), pp. 91–113].

Given a text string, a pattern string, and an integer k, a new algorithm for finding all occurrences of the pattern string in the text string with at most k differences is presented. Both its theoretical and practical variants improve upon the known algorithms.

of Results.We establish that several problems are highly parallelizable.For each of these problems, we design an optimal 0 (loglogn ) time parallel algorithm on the Common CRCW PRAM model which is the weakest among the CRCW PRAM models.These problems include: 0 all nearest smaller values, l preprocessing for answering range maxima queries, l several problems in Computational Geometry, l string matching.

The ( component ) merging problem is a new graph problem. Versions of this problem appear as bottlenecks in various graph algorithms. A new data structure solves this problem efficiently, and two special cases of the problem have even more efficient solutions based on other data structures. The performance of the data structures is sped up by introducing a new algorithmic tool called packets . The algorithms that use these solutions to the component merging problem also exploit new properties of two existing data structures. Specifically, Β-trees can be used simultaneously as a priority queue and a concatenable queue. Similarly, F-heaps support some kinds of split operations with no loss of efficiency. An immediate application of the solution to the simplest version of the merging problem is an Ο( t ( m , n )) algorithm for finding minimum spanning trees in undirected graphs without using F-heaps, where t ( m , n ) = m log 2 log 2 log d n , the graph has n vertices and m edges, and d = max( m / n , 2). Packets also improve the F-heap minimum spanning tree algorithm, giving the fastest algorithm currently known for this problem. The efficient solutions to the merging problem and the new observation about F-heaps lead to an Ο( n ( t ( m , n ) + n log n )) algorithm for finding a maximum weighted matching in general graphs. This settles an open problem posed by Tarjan [ 15, p. 123], where the weaker bound of O ( nm log ( n 2 / m )) was conjectured.

We show that the following statements are equivalent: Statement 1. 3-pushdown graphs have sublinear separators. Statement 1∗. k-page graphs have sublinear separators. Statement 2. A one-tape nondeterministic Turing machine can simulate a two-tape machine in subquadratic time. None of the statements is known to be true or false at present. However, our proof of equivalence is quantitative-it relates exactly the separator size of the two kinds of graphs to the running time of the simulation in Statement 2. Using this equivalence we derive several graph-theoretic corollaries. There are known examples where upper bounds on graph properties imply upper bounds on computation time or space. There are other examples where lower bounds on graph properties are used to derive lower bounds on computation time in restricted settings. However, our results may constitute the first example where a graph problem is shown to be equivalent to a problem in computational complexity. In a companion paper we construct graphs and prove a lower bound or their separators. Using the equivalence we prove an almost linear lower bound for the size of separators for 3-pushdown graphs and an almost quadratic lower bound for simulating two-tape nondeterministic Turing machines by one-tape machines. Specifically, for an integers s let ls(n), the s-iterated logarithm function, be defined inductively: l°(n)=n, ls+1(n)=log2(ls(n)) for s⩾0. Then: For every fixed s and all n, there is an n-vertex 3-pushdown graph whose smallest separator contains at least ω(n/ls(n)) vertices. There is a language L recognizable in real time by a two-tape nondeterministic Turing machine, but every on-line one-tape nondeterministic Turing machine that recognizes L requires ω(n2/ls(n)) time for any positive integer.

Interactive communication of knowledge from the point of view of resource-bounded computational complexity is studied. Extending the work of Goldwasser, Micali, and Rackof [Proc. 17th Annual ACM Symposium on the Theory of Computing, 1985, pp. 291–304; .,18 (1989), pp. 186–208], the authors define a protocol transferring the result of any fixed computation to be minimum-knowledge if it communicates no additional knowledge to the recipient besides the intended computational result. It is proved that such protocols may be combined in a natural way so as to build more complex protocols. A protocol is introduced for two parties, a prover and a verifier, with the following properties:(1) Following the protocol, the prover gives to the verifier a proof of the value, 0 or 1, of a particular Boolean predicate, which is (assumed to be) hard for the verifier to compute. Such a deciding “interactive proof-system” extends the interactive proof-systems of [op. cit.], which are used only to confirm that a certain predicate has value 1. (2) The protocol is minimum-knowledge. (3) The protocol is result-indistinguishable: an eavesdropper, overhearing an execution of the protocol, does not learn the value of the predicate that is proved. The value of the predicate is a cryptographically secure bit, shared by the two parties to the protocol. This security is achieved without the use of encryption functions, all messages being sent in the clear. These properties enable one to define a cryptosystem in which each user receives exactly the knowledge he is supposed to receive, and nothing more.

The problem of determining the cost of random-access memory (RAM) is addressed by studying the simulation of random addressing by a machine which lacks it, called a pointer machine. The model allows the use of a data type of choice. A RAM program of time t and space s can be simulated in O(t log s) time using a tree. However, this is not an obvious lower bound since a high-level data type can allow the data to be encoded in a more economical way. The major contribution is the formalization of incompressibility for general data types. The definition extends a similar property of strings that underlies the theory of Kolmogorov complexity. The main theorem states that for all incompressible data types an Omega (t log s) lower bound holds. Incompressibility is proved for the real numbers with a set of primitives which includes all functions which are continuously differentiable except on a countable closed set.>

A number of important computational problems in molecular biology, geology, speech recognition, and other areas can be expressed as recurrences which have typically been solved with dynamic programming. By using more sophisticated data structures, and by taking advantage of further structure from the applications, the authors speed up the computation of several of these recurrences by one or two orders of magnitude. The algorithms used are simple and practical.>

The minimum-cost flow problem is: Given a network with n vertices and m edges, find a maximum flow of minimum cost. Many network problems are easily reducible to this problem. A polynomial-time algorithm for the problem has been known for some time, but only recently a strongly polynomial algorithm was discovered. In this paper an O ( n 2 ( m + n log n )log n ) algorithm is designed. The previous best algorithm, due to Fujishige and Orlin, had an O ( m 2 ( m + n log n )log n ) time bound. Thus, for dense graphs an improvement of two orders of magnitude is obtained. The algorithm in this paper is based on Fujishige's algorithm (which is based on Tardos's algorithm). Fujishige's algorithm consists of up to m iterations, each consisting of O ( m log n ) steps. Each step solves a single source shortest path problem with nonnegative edge lengths. This algorithm is modified in order to make an improved analysis possible. The new algorithm may still consist of up to m iterations, and an iteration may still consist of up to O ( m log n ) steps, but it can still be shown that the total number of steps is bounded by O ( n 2 log n . The improvement is due to a new technique that relates the time spent to the progress achieved.

This paper surveys techniques for designing efficient sequential and parallel approximate string matching algorithms. Special attention is given to the methods for the construction of data structures that efficiently support primitive operations needed in approximate string matching.

We introduce new techniques for deriving lower bounds on the message complexity in asynchronous distributed computation. These techniques combine the choice of specific patterns of communication delays and crossing sequence arguments with consideration of the speed of propagation of messages, together with careful counting of messages in different parts of the network. They enable us to prove the following results, settling two open problems: An Ω(n log* n) lower bound for the number of messages sent by an asynchronous algorithm for computing any nonconstant function on a bidirectional ring of n anonymous processors. An Ω(n log n) lower bound for the average number of messages sent by any maximum finding algorithm on a ring of n processors, in case n is known.

This paper describes an O ( n 3 log n ) deterministic algorithm and an O ( n 3 ) Las Vegas algorithm for testing whether two given trivalent graphs on n vertices are isomorphic. In fact, the algorithms construct the set of all isomorphisms between two such graphs, presenting, in particular, generators for the group of all automorphisms of a trivalent graph. The algorithms are based upon the original polynomial-time solution to these problems by Luks but they introduce numerous speedups. These include improved permutation-group algorithms that exploit the structure of the underlying 2-groups. A remarkable property of the Las Vegas algorithm is that it computes the set of all isomorphisms between two trivalent graphs for the cost of computing only those isomorphisms that map a specified edge to a specified edge.

Two improved algorithms for string matching with k mismatches are presented. One algorithm is based on fast integer multiplication algorithms whereas the other follows more closely classic string-matching techniques.

In this paper we consider a synchronous broadcasting network, a distributed computation model which represents communication networks that are used extensively in practice. We consider a basic problem of information sharing: the computation of the multiple identification function. That is, given a network of p processors, each of which contains an n-bit string of information, how can every processor compute efficiently the subset of processors which have the same information as itself? The problem was suggested by Yao as a generalization of the two-processor case studied in his classic paper on distributed computing (Yao, 1979). The naive way to solve this problem takes O(np) communication time, where a time unit is the time to transfer one bit. We present an algorithm which takes advantage of properties of strings and is O(n log2 p + p) time. A simulation of sorting networks by the distributed model yields an O(n log p + p) (impractical) algorithm. By applying Yao's probabilistic implementation of the two-processor case to both algorithm we get probabilistic versions (with small error) where n is replaced by log n in the complexity expressions. We also present lower bounds for the problem: an Ω(n) and an Ω(p) bound are shown.

The minimum-cost flow problem is the following: given a network with n vertices and m edges, find a maximum flow of minimum cost. Many network problems are easily reducible to this problem. A polynomial-time algorithm for the problem has been known for some time [EK], but only recently a strongly polynomial algorithm was discovered [Ts]. In this paper we design an O(n2(m + n log n)log n) algorithm. The previous best algorithm had an O(m2 (m + n log n) log n) time bound ([F], [O]). Thus, we obtain an improvement of two orders of magnitude for dense graphs. Our algorithm is based on Fujishige's algorithm [F] (which is based on Tardos' algorithm [Ts]). Fujishige's algorithm consists of up to O(m log n) steps. Each step solves a single source shortest path problem with nonnegative edge lengths. We modify this algorithm in order to make an improved analysis possible. The new algorithm may still consist of up to m iterations, and an iteration may still consist of up to O(m log n) steps, but we can still show that the total number of steps is bounded by O(n2 log n). The improvement is due to a new technique that relates the time spent to the progress achieved.

We show that the following statements are equivalent :Statement 1: 3-pushdown graphs have sublinear separators.

We define two generalized types of a priority queue by allowing some forms of changing the priorities of the elements in the queue. We show that they can be implemented efficiently. Consequently, each operation takes $O(\log n)$ time. We use these generalized priority queues to construct an $O(EV\log V)$ algorithm for finding a maximal weighted matching in general graphs.

We define a graph problem which we refer to as the component merging problem. Versions of the problem appear as bottlenecks in various graph algorithms. We show how to solve an important special case of the problem.

We prove the following four results on communication complexity:

Let WRAM [PRAM] be a parallel computer with p processors (RAM's) which share a common memory and are allowed simultaneous reads and writes [only simultaneous reads]. The only type of simultaneous writes allowed is a simultaneous AND: several processors may write O simultaneously into the same memory cell. Let t be the time bound of the computer. We design below families of parallel algorithms that solve the string matching problem with inputs of size n (n is the sum of lengths of the pattern and the text) and have the following performance in terms of p, t and n:

It is known that k tapes are no better than two tapes for nondeterministic machines. We show here that two tapes are better than one. In fact, we show that two pushdown stores are better than one tape. Also, k tapes are no better than two for nondeterministic reversal-bounded machines; and we show that even two reversal-bounded pushdown stores are better than one reversal-bounded tape. We also show that for one-tape nondeterministic machines, unrestricted operation is better than reversal-bounded operation.

We prove the following lower bounds for on line computation.

The question of what is a good way to interconnect a large number of processors is investigated The roam result is the construction of a universal parallel machine that can simulate every reasonable parallel machine with only a small loss of time and with essentially the same number of processors.

The main results of this paper are an O(n3) probabilistic algorithm and an O(n3 log n) deterministic algorithm that test whether two given trivalent graphs are isomorphic. In fact, the algorithms construct the set of all isomorphisms of the two graphs. Variants of these algorithms construct the set of all automorphisms of a trivalent graph. The algorithms make use of some new improved permutation group algorithms that exploit the fact that the groups involved are 2-groups. A remarkable property of the probabilistic algorithm is that it computes Isoe,ei(X,Y), i = 1,...,m, m = O(n) (the set of all isomorhisms φ: X → Y with φ(e)=ei) for the cost of computing the single set Isoe,el(X,Y).

We define two generalized types of a priority queue by allowing some forms of changing the priorities of the elements in the queue. We show that they can be implemented efficiently. Consequently, each operation takes O(log n) time. We use these generalized priority queues to construct an O(EV log V) algorithm for finding a maximal weighted matching in general graphs.

It is known that k tapes are no better than two tapes for nondeterministic machines. We show here that two tapes are better than one. In fact, we show that two pushdown stores are better than one tape. Also, k tapes are no better than two for nondeterministic reversal-bounded machines. We show here that two tapes are better than one for such machines. In fact, we show that two reversal-bounded pushdown stores are better than one reversal-bounded tape. We also show that for one-tape nondeterministic machines, unrestricted machines are better than reversal-bounded machines.

All algonthm that constructs, for a given set of (functional and multwalued) dependen-cJes X and a set of attributes X, the dependency basis of X as described.The algorithm runs in time O(( 1+ min(E, logp))llZl[), where p is the number of sets m the dependency basas of X,/~ Js the number of multivalued dependencies in X, and IlXll as the length of ~. a A variant of the algorithm tests whether a dependency a is unplied by X m time O((1 + mm(/~, log p-))ll~.ll),where ff is the number of sets m the dependency basas of the left-hand side of o that intersect the right-hand sade of o Whenever all the dependencies in X are functaonal dependenoes, these algorithms are linear Ume Categories and Subject Descriptors.F.

We define a language L and show that its time and space complexities T and S must satisfy T2S ≥ cn3 even allowing machines with multiple (non random) access to the input.

We define a language L and show that is cannot be recognized by any two way deterministic counter machine. It is done by fooling any given such machine; i.e. showing that if it accepts L' ⊇ L, then L'-L ≠ φ. For this purpose, an argument stronger than the well known crossing sequence argument needs to be introduced. Since L is accepted by a two-way deterministic pushdown automaton, we consequently show that one pushdown stack is more powerful than one counter for deterministic two-way machines.

In this paper we investigate the question of what is a good way to interconnect a large number of processors. Our main result is the construction of a universal parallel machine that can simulate every reasonable parallel machine with only a small loss of time and with essentially the same number of processors.

In this paper we describe a new linear-time string-matching algorithm requiring neither dynamic storage allocation nor other high-level capabilities. The algorithm can be implemented to run in linear time even on a six-head two-way finite automaton. Moreover, the automaton requires only “{= , ≠}- branching” [1]. (Decisions depend on which of the six scanned pattern or text symbols and positions are the same, but not on the particular symbols or how many symbols there are. Hence the same algorithm works even for an infinite alphabet.) A “real-time” implementation is possible on such a multihead finite automaton with a few more heads.

A sufficient condition for an on-line algorithm to be transformed into a real-time algorithm is given.This condition is used to construct real-time algorithms for various string-matching problems by random access machines and by Turing machines.

New implementation of known algorithms improve the running time of the best known algorithms for finding the vertex connectivity of undirected and directed graphs.

The string-matching problem is to find all instances (as contiguous substrings) of a “pattern” character string x in a longer “text" string ”. The naive algorithm, trying the pattern from scratch starting at each successive text position, requires only a fixed number of auxiliary storage locations but time proportional to $|x|\cdot|Y|$ (worst case). On the other hand, the fast algorithm of Knuth, Morris, and Pratt requires only time proportional to $|Y|$ but extra space proportional to $|x|$ (every case). Algorithms described in this paper reduce the extra space used by the Knuth–Morris–Pratt algorithm down to $O(\log |x|)$, and the time for the naive algorithm down to $O(|x|^\varepsilon |y|)$ for any fixed $\varepsilon > 0$. Also described are implementations on two-way multihead finite automata and multitape Turing machines.

An O(EVlog2V) algorithm for finding the maximal flow in networks is described. It is asymptotically better than the other known algorithms if E = O(V2-ε) for some ε>0. The analysis of the running time exploits the discovery of a phenomenon similar to (but more general than) path compression, although the union find algorithm is not used. The time bound is shown to be tight in terms of V and E by exhibiting a family of networks that require Ω(EVlog2V) time.++

We review the motivation underlying the study of data encodings and the formal framework of the study. We then present a series of results whose main message is that (complete) trees are materially less congenial storage representations for tree-like data structures than they have been shown to be for array-like data structures. In response to these results, we propose a new data structure, called a dree, which we show to share the advantages of trees, but not to suffer their disadvantages, when used as a storage structure.

An algonthm ,s developed which finds the nth largest element of a linearly ordered set S, given m the form of m patrwise disjoint subsets Each of the m subsets satisfies the property that its kth largest element can be computed m a constant amount of time The algorithm terminates m time O(m.log2([Sj/m))The selection algorithm applies to the problem of optimum distribution of effort, namely, the maxun~zation of the total utility of allocating n persons to m activities, where the utlhty of k persons assigned to actwity j ~s a concave funcuon uAk) Consequently, this problem can be solved m time O(m.logZn)

A new algorithm for finding the maximal flow in a given network is presented. The algorithm runs in time O(V5/3E2/3) or O(n2.33) where n = V + E is the length of the input.

Let P1 = {w ~ X*:w = w R, [w I > 1} be the set of all nontnvial pahndromes over X A hneartime on-hne recogmtmn algorithm is presented for P~ ("palstar") on a random-access machine with addmon and umform cost criterion Also presented are a hnear-tlme on-line recognmon algorithm for P~ on a muitltape Turmg machine and a recognition algorithm for Pt 2 on a two-way deterministic pushdown automaton.The correctness of these algorithms is based on new "cancellation iemmas" for the languages P~ and P~

The string-matching problem is to find all instances (as contiguous substrings) of a “pattern” character string x in a longer “text string ”. The naive algorithm, trying the pattern from scratch starting at each successive text position, requires only a fixed number of auxiliary storage locations but time proportional to $|x|\cdot|Y|$ (worst case). On the other hand, the fast algorithm of Knuth, Morris, and Pratt requires only time proportional to $|Y|$ but extra space proportional to $|x|$ (every case). Algorithms described in this paper reduce the extra space used by the Knuth–Morris–Pratt algorithm down to $O(\log |x|)$, and the time for the naive algorithm down to $O(|x|^\varepsilon |y|)$ for any fixed $\varepsilon > 0$. Also described are implementations on two-way multihead finite automata and multitape Turing machines.

Several procedures based on (not necessarily regular) resolution for checking whether a formula in CF3 is contradictory are considered. The procedures use various methods of bounding the size of the clauses which are generated. The following results are obtained: 1. All of the proposed procedures which are forced to run in polynomial time do not always work—i.e., they do not identify all contradictory formulas. 2. Those which always work must run in exponential time. The exponential lower bounds for these procedures do not follow directly from Tseitin’s lower bound for regular resolution since these procedures also allow nonregular resolution trees.

Let P1 = {w ε Σ*:w = wR, |w| ≫ 1} be the set of all nontrivial palindromes over Σ. In Part I, we present a linear-time on-line recognition algorithm for P1* ("palstar") on a random-access machine with addition and uniform cost criterion. We also present a lineartime on-line recognition algorithm for P12 on a multitape Turing machine and a recognition algorithm for P12 on a two-way deterministic pushdown automaton. The correctness of these algorithms is based on new "cancellation lemmas" for the languages P1* and P12. In Part II, we present real-time recognition algorithms for the languages {wxyxz ε Σ*: |w|=r|x|, |y|=s|x|, |z|=t|x|} and {wxyxRz ε Σ*: |w|=r|x|, |y|=s|x|, |z|=t|x|} on multitape Turing machines, for arbitrary fixed r, s, and t.

We give a sufficient condition when an on-line algorithm can be transformed into a real-time algorithm. We use this condition to construct real-time algorithms for string-matching and palindrome recognition problems by random access machines and by Turing machines.

Several procedures based on (not necessarily regular) resolution for checking whether a formula in CN3 is contradictory are considered. The procedures use various methods of bounding the size of the clauses which are generated. The following results are obtained: 1) All of the proposed procedures which are forced to run in polynomial time do not always work—i.e., they do not identify all contradictory formulas. 2) Those which always work must run in exponential time. The exponential lower bounds for these procedures do not follow from Tseitin's lower bound for regular resolution since these procedures also allow nonregular resolution trees.