Routing multiple paths in hypercubes

We present new techniques for mapping computations onto hypercubes. Our methods speed up classical implementations of grid and tree communications by a factor of (n), wheren is the number of hypercube dimensions. The speedups are asymptotically the best possible.We obtain these speedups by mapping each edge of the guest graph onto short, edge-disjoint paths in the hypercube such that the maximum congestion on any hypercube edge isO(1). These multiple-path embeddings can be used to reduce communication time for large grid-based scientific computations, to increase tolerance to link faults, and for fast routing of large messages.We also develop a general technique for deriving multiple-path embeddings from multiple-copy embeddings. Multiple-copy embeddings are one-to-one maps of independent copies of the guest graph within the hypercube. We present an efficient multiple-copy embedding of the cube-connected-cycles network within the hypercube. This embedding is used to derive efficient multiple-path embeddings of trees and butterfly networks in hypercubes.This research was supported by NSF/DARRA Grant CCR-8908285, NSF Grant CCR-8807426, and AFOSR Grant 89-0382.     

Finding all periods and initial palindromes of a string in parallel

An optimalO(log logn)-time CRCW-PRAM algorithm for computing all period lengths of a string is presented. Previous parallel algorithms compute the period only if it is shorter than half of the length of the string. The algorithm can be used to find all initial palindromes of a string in the same time and processor bounds. Both algorithms are the fastest possible over a general alphabet. We derive a lower bound for finding initial palindromes by modifying a known lower bound for finding the period length of a string [9]. Whenp processors are available the bounds become (n/p+log_1+p/n2p).This work was partially supported by NSF Grant CCR-90-14605. D. Breslauer was partially supported by an IBM Graduate Fellowship while studying at Columbia University and by a European Research Consortium for Informatics and Mathematics postdoctoral fellowship.     

Single-exception sorting networks and the computational complexity of optimal sorting network verification

Asorting network is a combinational circuit for sorting constructed from comparison-swap units. The depth of such a circuit is a measure of its running time. It is known that sorting-network verification is computationally intractable. However, it is reasonable to hypothesize that only the fastest (that is, the shallowest) networks are likely to be fabricated. It is shown that the verification of shallow sorting networks is also computationally intractable. Firstly, a method for constructing asymptotically optimalsingle-exception sorting networks is demonstrated. These are networks which sort all zero-one inputs except one. More specifically, their depth isD(n-1)+2log(n-1)+2, whereD(n) is the minimum depth of ann-input sorting network. It follows that the verification problem for sorting networks of depth 2D(n)+6logn+O(1) is Co-NP complete. Given the current state of knowledge aboutD(n) for largen, this indicates that the complexity of verification for shallow sorting networks is as great as for deep networks.This research was supported by NSF Grant CCR-8801659.     

Optimal multilayer channel routing with overlap

This paper presents algorithms for multiterminal net channel routing where multiple interconnect layers are available. Major improvements are possible if wires are able to overlap, and our generalized main algorithm allows overlap, but only on everyKth (K 2) layer. Our algorithm will, for a problem with densityd onL layers,L K + 3,provably use at most three tracks more than optimal: (d + 1)/L/K + 2 tracks, compared with the lower bound of d/L/K. Our algorithm is simple, has few vias, tends to minimize wire length, and could be used if different layers have different grid sizes. Finally, we extend our algorithm in order to obtain improved results for adjacent (K = 1) overlap: (d + 2)/2L/3 + 5 forL 7.This work was supported by the Semiconductor Research Corporation under Contract 83-01-035, by a grant from the General Electric Corporation, and by a grant at the University of the Saarland.     

On reducing the number of states in a PDA

A transformation is presented which converts any pushdown automaton (PDA)M ₀ withn ₀ states andp ₀ stack symbols into an equivalent PDAM withn states and n ₀ /n² p ₀ stack symbols into an equivalent ofn, 1n ₀. This transformation preserves realtime behavior but not derterminism. The transformation is proved to be the best possible one in the following sense: for each choice of the parametersn ₀ + 1 stack symbols for any desired value realtime PDAM ₀ such that any equivalent PDAM (whether realtime or not) havingn states must have at least (n ₀ /n)² p₀ stack symbols. Furthermore, the loss of deterministic behavior cannot be avoided, since for each choice ofn ₀ andp ₀, there is a deterministic PDAM ₀ such that no equivalent PDAM with fewer states can be deterministic.This research was supported in part by the National Science Foundation under Grants MCS76-10076 and MCS76-10076A01.     

A semidynamic construction of higher-order voronoi diagrams and its randomized analysis

Thek-Delaunay tree extends the Delaunay tree introduced in [1], and [2]. It is a hierarchical data structure that allows the semidynamic construction of the higher-order Voronoi diagrams of a finite set ofn points in any dimension. In this paper we prove that a randomized construction of thek-Delaunay tree, and thus of all the orderk Voronoi diagrams, can be done inO(n logn+k ³n) expected time and O(k²n) expected storage in the plane, which is asymptotically optimal for fixedk. Our algorithm extends tod-dimensional space with expected time complexityO(k ^(d+1)/2+1 n ^(d+1)/2) and space complexityO(k ^(d+1)/2 n ^(d+1)/2). The algorithm is simple and experimental results are given.This work has been supported in part by the ESPRIT Basic Research Action No. 3075 (ALCOM).     

Generating binary trees of bounded height

Summary We present a new encoding scheme for binary trees with n internal nodes whose heights are bounded by a given value h, hlog₂(n +1)1. The scheme encodes the internal nodes of the tree level by level and enables us to develop an algorithm for generating all binary trees within this class in a certain predetermined order. Specifically, the trees are generated in decreasing height and for trees of the same height they are generated in lexicographically increasing order. The algorithm can be easily generalized to encompass t-ary trees with bounded height. It is then shown that the average generation time per tree is constant (independent of n and h).Supported in part by National Science Foundation under Grants MCS 8342682 and ECS 8340031     

The input/output complexity of transitive closure

Suppose a directed graph has its arcs stored in secondary memory, and we wish to compute its transitive closure, also storing the result in secondary memory. We assume that an amount of main memory capable of holdings values is available, and thats lies betweenn, the number of nodes of the graph, ande, the number of arcs. The cost measure we use for algorithms is theI/O complexity of Kung and Hong, where we count 1 every time a value is moved into main memory from secondary memory, or vice versa.In the dense case, wheree is close ton ², we show that I/O equal toO(n ³/s) is sufficient to compute the transitive closure of ann-node graph, using main memory of sizes. Moreover, it is necessary for any algorithm that is standard, in a sense to be defined precisely in the paper. Roughly, standard means that paths are constructed only by concatenating arcs and previously discovered paths. For the sparse case, we show that I/O equal toO(n ²e/s) is sufficient, although the algorithm we propose meets our definition of standard only if the underlying graph is acyclic. We also show that(n ²e/s) is necessary for any standard algorithm in the sparse case. That settles the I/O complexity of the sparse/acyclic case, for standard algorithms. It is unknown whether this complexity can be achieved in the sparse, cyclic case, by a standard algorithm, and it is unknown whether the bound can be beaten by nonstandard algorithms.We then consider a special kind of standard algorithm, in which paths are constructed only by concatenating arcs and old paths, never by concatenating two old paths. This restriction seems essential if we are to take advantage of sparseness. Unfortunately, we show that almost another factor ofn I/O is necessary. That is, there is an algorithm in this class using I/OO(n ³e/s) for arbitrary sparse graphs, including cyclic ones. Moreover, every algorithm in the restricted class must use(n ³e/s/log³ n) I/O, on some cyclic graphs.The work of this author was partially supported by NSF grant IRI-87-22886, IBM contract 476816, Air Force grant AFOSR-88-0266 and a Guggenheim fellowship.     

System Diagnosis of the Failed Modules and Connections in Hypercube Structures of the Multiprocessor Computer Systems

Combinations of failed components (modules and communication lines) for which the n-cube is not an n-singlefold diagnosable system were shown to be possible in the hypercube structures. A system of n chains of a certain structure constructed to check each of the N(= 2_n) hypercube modules was used to transform the initial information about the state of the hypercube. A two-stage procedure for diagnosis of p( n) failed components was substantiated. Its application to some failure situations in the vertex 3-cube was illustrated.     

A note on embeddings among folded hypercubes,even graphs and odd graphs

In this short note, we establish topological relationships among the folded hypercube FQ _n , the even graph E _k and the odd graphs O _d via embedding. Such embeddings are measured via dilation.     

Multilayer grid embeddings for VLSI

In this paper we propose two new multilayer grid models for VLSI layout, both of which take into account the number of contact cuts used. For the first model in which nodes exist only on one layer, we prove a tight area × (number of contact cuts) = (n ²) tradeoff for embeddingn-node planar graphs of bounded degree in two layers. For the second model in which nodes exist simultaneously on all layers, we give a number of upper bounds on the area needed to embed groups using no contact cuts. We show that anyn-node graph of thickness 2 can be embedded on two layers inO(n ²) area. This bound is tight even if more layers and any number of contact cuts are allowed. We also show that planar graphs of bounded degree can be embedded on two layers inO(n ^3/2(logn)²) area.Some of our embedding algorithms have the additional property that they can respect prespecified grid placements of the nodes of the graph to be embedded. We give an algorithm for embeddingn-node graphs of thicknessk ink layers usingO(n ³) area, using no contact cuts, and respecting prespecified node placements. This area is asymptotically optimal for placement-respecting algorithms, even if more layers are allowed, as long as a fixed fraction of the edges do not use contact cuts. Our results use a new result on embedding graphs in a single-layer grid, namely an embedding ofn-node planar graphs such that each edge makes at most four turns, and all nodes are embedded on the same line.The first author's research was partially supported by NSF Grant No. MCS 820-5167.     

Rational Interpolation from Stochastic Data: A New Froissart's Phenomenon

The analytic structure of Rational Interpolants (R.I.) f (z) built from randomly perturbed data is explored; the interpolation nodes x _j , j = 1,...,M, are real points where the function f reaches these prescribed data . It is assumed that the data are randomly perturbed values of a rational function _(n) ^(m) (m / n is the degree of the numerator/denominator). Much attention is paid to the R.I. familyf _(n+1) ^(m–1), in the small stochasticity régime. The main result is that the additional zero and pole are located nearby the root of the same random polynomial, called the Froissart Polynomial (F.P.). With gaussian hypothesis on the noise, the random real root of F.P. is distributed according to a Cauchy-Lorentz law, with parameters such that the integrated probability over the interpolation interval x ₁, x _M is always larger than 1/2; in two cases studied in detail, it reaches 2/3 in one case and almost 3/4 in the other. For the families f _(n+k) ^(m+k), numerical explorations point to similar phenomena; inspection shows that, in the mean, the localization occurs in the complex and/or real vicinity of the interpolation interval.     

Tight bounds for oblivious routing in the hypercube

We prove that in anyN-node communication network with maximum degreed, any deterministic oblivious algorithm for routing an arbitrary permutation requires (N/d) parallel communication steps in the worst case. This is an improvement upon the (N/d ^3/2) bound obtained by Borodin and Hopcroft. For theN-node hypercube, in particular, we show a matching upper bound by exhibiting a deterministic oblivious algorithm that routes any permutation in (N/logN) steps. The best previously known upper bound was (N). Our algorithm may be practical for smallN (up to about 2¹⁴ nodes).C. Kaklamanis was supported in part by NSF Grant NSF-CCR-87-04513. T. Tsantilas was supported in part by NSF Grants NSF-DCR-86-00379 and NSF-CCR-89-02500.     

A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs

Algorithms used in data mining and bioinformatics have to deal with huge amount of data efficiently.In many applications,the data are supposed to have explicit or implicit structures.To develop efficient algorithms for such data,we have to propose possible structure models and test if the models are feasible.Hence,it is important to make a compact model for structured data,and enumerate all instances efficiently.There are few graph classes besides trees that can be used for a model.In this paper,we inves...     

A Low-Cost Fault-Tolerant Structure for the Hypercube

We propose a new, low-cost fault-tolerant structure for the hypercube that employs spare processors and extra links. The target of the proposed structure is to fully tolerate the first faulty node, no matter where it occurs, and almost fully tolerate the second, meaning that the underlying hypercube topology can be resumed if the second faulty node occurs at most locations—expectantly 92% of locations. The unique features of our structure are that (1) it utilizes the unused extra link-ports in the processor nodes of the hypercube to obtain the proposed topology, so that minimum extra hardware is needed in constructing the fault-tolerant structure and (2) the structure's node-degrees are low as desired—the primary and spare nodes all have node-degrees of n + 2 for an n-dimensional hypercube. The number of spare nodes is one fourth of primary nodes. The reconfiguration algorithm in the presence of faults is elegant and efficient. The proposed structure also effectively enhances the diagnosability of the hypercube system. It is shown that the diagnosability of the structure is increased to n + 2, whereas an ordinary n-dimensional hypercube has diagnosability n.     

On the oracle complexity of factoring integers

The problem of factoring integers in polynomial time with the help of an infinitely powerful oracle who answers arbitrary questions with yes or no is considered. The goal is to minimize the number of oracle questions. LetN be a given compositen-bit integer to be factored, wheren = log₂ N. The trivial method of asking for the bits of the smallest prime factor ofN requiresn/2 questions in the worst case. A non-trivial algorithm of Rivest and Shamir requires onlyn/3 questions for the special case whereN is the product of twon/2-bit primes. In this paper, a polynomial-time oracle factoring algorithm for general integers is presented which, for any >0, asks at most n oracle questions for sufficiently largeN, thus solving an open problem posed by Rivest and Shamir. Based on a plausible conjecture related to Lenstra's conjecture on the running time of the elliptic curve factoring algorithm, it is shown that the algorithm fails with probability at mostN ^–/2 for all sufficiently largeN.     

The complexity of drawing trees nicely

Summary We investigate the complexity of producing aesthetically pleasing drawings of binary trees, drawings that are as narrow as possible. The notion of what is aesthetically pleasing is embodied in several constraints on the placement of nodes, relative to other nodes. Among the results we give are: (1) There is no obvious principle of optimality that can be applied, since globally narrow, aesthetic placements of trees may require wider than necessary subtrees. (2) A previously suggested heuristic can produce drawings on n-node trees that are (n) times as wide as necessary. (3) The problem can be reduced in polynomial time to linear programming; hence, if the coordinates assigned to the nodes are continuous variables, then the problem can be solved in polynomial time. (4) If the placement is restricted to the integral lattice then the problem is NP-hard, as is its approximation to within a factor of about 4 per cent.This research was supported in part by the National Science Foundation, grant numbers NSF MCS 77-22830, NSF MCS 79-04897, and NSF MCS 81-17364     

A 2n−2 step algorithm for routing in ann ×n array with constant-size queues

In this paper we describe a deterministic algorithm for solving any 1–1 packet-routing problem on ann ×n mesh in 2n–2 steps using constant-size queues. The time bound is optimal in the worst case. The best previous deterministic algorithm for this problem required time 2n+(n/q) using queues of size (q) for any 1qn, and the best previous randomized algorithm required time 2n+(logn) using constant-size queues.This research was supported by the Clear Center at UTD, DARPA Contracts N00014-91-J-1698 and N00014-92-J-1799, Air Force Contract F49620-92-J-0125, Army Contract DAAL-03-86-K-0171, an NSF Presidential Young Investigator Award with matching funds from AT&T and IBM, and by the Texas Advanced Research Program under Grant No. 3972. A preliminary version of this paper appeared in [5].     

An optimal parallel algorithm for planar cycle separators

We present an optimal parallel algorithm for computing a cycle separator of ann-vertex embedded planar undirected graph inO(logn) time onn/logn processors. As a consequence, we also obtain an improved parallel algorithm for constructing a depth-first search tree rooted at any given vertex in a connected planar undirected graph in O(log² n) time on n/logn processors. The best previous algorithms for computing depth-first search trees and cycle separators achieved the same time complexities, but withn processors. Our algorithms run on a parallel random access machine that permits concurrent reads and concurrent writes in its shared memory and allows an arbitrary processor to succeed in case of a write conflict.A preliminary version of this paper appeared as Improved Parallel Depth-First Search in Undirected Planar Graphs in theProceedings of the Third Workshop on Algorithms and Data Structures, 1993, pp. 407–420.Supported in part by NSF Grant CCR-9101385.     

Minimum Weakly Fundamental Cycle Bases Are Hard To Find

In the last years, new variants of the minimum cycle basis (MCB) problem and new classes of cycle bases have been introduced, as motivated by several applications from disparate areas of scientific and technological inquiry. At present, the complexity status of the MCB problem is settled only for undirected, directed, and strictly fundamental cycle bases (SFCB’s). Weakly fundamental cycle bases (WFCB’s) form a natural superclass of SFCB’s. A cycle basis of a graph G is a WFCB iff ν=0 or there exists an edge e of G and a circuit C _i in such that is a WFCB of G∖e. WFCB’s still possess several of the nice properties offered by SFCB’s. At the same time, several classes of graphs enjoying WFCB’s of cost asymptotically inferior to the cost of the cheapest SFCB’s have been found and exhibited in the literature. Considered also the computational difficulty of finding cheap SFCB’s, these works advocated an in-depth study of WFCB’s. In this paper, we settle the complexity status of the MCB problem for WFCB’s (the MWFCB problem). The problem turns out to be -hard. However, in this paper, we also offer a simple and practical 2⌈log ₂ n⌉-approximation algorithm for the MWFCB problem. In O(n ν) time, this algorithm actually returns a WFCB whose cost is at most 2⌈log ₂ n⌉∑ _e∈E(G) w _e , thus allowing a fast 2⌈log ₂ n⌉-approximation also for the MCB problem. With this algorithm, we provide tight bounds on the cost of any MCB and MWFCB.