Finding Edge-Disjoint Paths in Partial k -Trees

For a given graph G and p pairs (s _i ,t _i ) , , of vertices in G , the edge-disjoint paths problem is to find p pairwise edge-disjoint paths P _i , , connecting s _i and t _i . Many combinatorial problems can be efficiently solved for partial k -trees (graphs of treewidth bounded by a fixed integer k ), but the edge-disjoint paths problem is NP-complete even for partial 3 -trees. This paper gives two algorithms for the edge-disjoint paths problem on partial k -trees. The first one solves the problem for any partial k -tree G and runs in polynomial time if p=O( log n) and in linear time if p=O(1) , where n is the number of vertices in G . The second one solves the problem under some restriction on the location of terminal pairs even if . Received January 21, 1977; revised September 19, 1997.     

Parallel Construction of (a, b)-Trees

We present an optimal parallel algorithm for the construction of (a, b)-trees-a generalization of 2-3 trees, 2-3-4 trees, and B-trees. We show the existence of a canonical form for (a, b)-trees, with a very regular structure, which allows us to obtain a scalable parallel algorithm for the construction of a minimum-height (a, b)-tree with N keys in O(N/p + log log N) time using p ≤ N/log log N processors on the EREW-PRAM model, and in O(N/p) time using p ≤ N processors on the CREW model. We show that the average memory utilization for the canonical form is at least 50% better than that for the worst-case and is also better than that for a random (a, b)-tree. A significant feature of the proposed parallel algorithm is that its time-complexity depends neither on a nor on b, and hence our general algorithm is superior to earlier algorithms for parallel construction of B-trees.     

L(2, 1)-labellings for direct products of a triangle and a cycle

An L(2, 1)-labelling of a graph G is a vertex labelling such that the difference of the labels of any two adjacent vertices is at least 2 and that of any two vertices of distance 2 is at least 1. The minimum span of all L(2, 1)-labellings of G is the λ-number of G and denoted by λ(G). Lin and Lam computed λ(G) for a direct product G=K _m ×P _n of a complete graph K _m and a path P _n . This is a natural lower bound of λ(K _m ×C _n ) for a cycle C _n . They also proved that when n≡ 0±od 5m, this bound is the exact value of λ(K _m ×C _n ) and computed the value when n=3, 5, 6. In this article, we compute the λ-number of G, where G is the direct product K ₃×C _n of the triangle and a cycle C _n for all the other n. In fact, we show that among these n, λ(K ₃×C _n )=7 for all n≠7, 11 and λ(K ₃×C _n )=8 when n=7, 11.     

Cartesian graph factorization at logarithmic cost per edge

LetG be a connected graph withn vertices andm edges. We develop an algorithm that finds the (unique) prime factors ofG with respect to the Cartesian product inO(m logn) time andO(m) space. This shows that factoringG is at most as costly as sorting its edges. The algorithm gains its efficiency and practicality from using only basic properties of product graphs and simple data structures.     

Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs

We present an efficient algorithm for 4-coloring perfect planar graphs. The best previously known algorithm for this problem takesO(n ^3/2) sequential time, orO(log⁴ n) parallel time withO(n³) processors. The sequential implementation of our algorithm takesO(n logn) time. The parallel implementation of our algorithm takesO(log³ n) time withO(n) processors on a PRAM.     

Diameter variability of cycles and tori

The diameter of a graph is an important factor for communication as it determines the maximum communication delay between any pair of processors in a network. Graham and Harary [N. Graham, F. Harary, Changing and unchanging the diameter of a hypercube, Discrete Applied Mathematics 37/38 (1992) 265-274] studied how the diameter of hypercubes can be affected by increasing and decreasing edges. They concerned whether the diameter is changed or remains unchanged when the edges are increased or decreased. In this paper, we modify three measures proposed in Graham and Harary (1992) to include the extent of the change of the diameter. Let D^-k(G) is the least number of edges whose addition to G decreases the diameter by (at least) k, D⁺⁰(G) is the maximum number of edges whose deletion from G does not change the diameter, and D^+k(G) is the least number of edges whose deletion from G increases the diameter by (at least) k. In this paper, we find the values of D^-k(C_m), D^-1(T_m,n), D^-2(T_m,n), D⁺¹(T_m,n), and a lower bound for D⁺⁰(T_m,n) where C_m be a cycle with m vertices, T_m,n be a torus of size m by n.     

Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs

We present an efficient algorithm for 4-coloring perfect planar graphs. The best previously known algorithm for this problem takesO(n ^3/2) sequential time, orO(log⁴ n) parallel time withO(n³) processors. The sequential implementation of our algorithm takesO(n logn) time. The parallel implementation of our algorithm takesO(log³ n) time withO(n) processors on a PRAM.

     

Efficient parallel algorithms forr-dominating set andp-center problems on trees

We develop efficient parallel algorithms for ther-dominating set and thep-center problems on trees. On a concurrent-read exclusive-write PRAM, our algorithm for ther-dominating set problem runs inO(logn log logn) time withn processors. The algorithm for thep-center problem runs inO(log² n log logn) time withn processors.Xin He was supported in part by an Ohio State University Presidential Fellowship, and by the Office of Research and Graduate Studies of Ohio State University. Yaacov Yesha was supported in part by the National Science Foundation under Grant No. DCR-8606366.     

Fast Parallel Reordering and Isomorphism Testing of k -Trees

Abstract. In this paper two problems on the class of k -trees, a subclass of the class of chordal graphs, are considered: the fast reordering problem and the isomorphism problem. An O(log ² n) time parallel algorithm for the fast reordering problem is described that uses O(nk(n-k)/\kern -1ptlog n) processors on a CRCW PRAM proving membership in the class NC for fixed k . An O(nk(k+1)!) time sequential algorithm for the isomorphism problem is obtained representing an improvement over the O(n ² k(k+1)!) algorithm of Sekharan (the second author) [10]. A parallel version of this sequential algorithm is presented that runs in O(log ² n) time using O((nk((k+1)!+n-k))/log n) processors improving on a parallel algorithm of Sekharan for the isomorphism problem [10]. Both the sequential and parallel algorithms use a concept introduced in this paper called the kernel of a k -tree.     

Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree

The vertex updating problem for a minimum spanning tree (MST) is defined as follows: Given a graphG=(V, E _G) and an MSTT forG, find a new MST forG to which a new vertexz has been added along with weighted edges that connectz with the vertices ofG. We present a set of rules that produce simple optimal parallel algorithms that run inO(lgn) time usingn/lgn EREW PRAM processors, wheren=¦V¦. These algorithms employ any valid tree-contraction schedule that can be produced within the stated resource bounds. These rules can also be used to derive simple linear-time sequential algorithms for the same problem. The previously best-known parallel result was a rather complicated algorithm that usedn processors in the more powerful CREW PRAM model. Furthermore, we show how our solution can be used to solve the multiple vertex updating problem: Update a given MST whenk new vertices are introduced simultaneously. This problem is solved inO(lgk·lgn) parallel time using (k·n)/(lgk·lgn) EREW PRAM processors. This is optimal for graphs having (kn) edges.Part of this work was done while P. Metaxas was with the Department of Mathematics and Computer Science, Dartmouth College.     

Inverse degree and super edge-connectivity

Let G be a connected graph of order n, minimum degree δ(G) and edge connectivity λ(G). The graph G is called maximally edge-connected if λ(G)=δ(G), and super edge-connected if every minimum edge-cut consists of edges incident with a vertex of minimum degree. Define the inverse degree of G with no isolated vertices as R(G)=∑ _v∈V(G)1/d(v), where d(v) denotes the degree of the vertex v. We show that if R(G)<2+(n?2δ)/(n?δ) (n?δ?1), then G is super edge-connected. We also give an analogous result for triangle-free graphs.     

A chained-matrices approach for parallel computation of continued fractions and its applications

A chained-matrices approach for parallel computing thenth convergent of continued fractions is presented. The resulting algorithm computes the entire prefix values of any continued fraction inO(logn) time on the EREW PRAM model or a network withO(n/logn) processors connected by the cube-connectedcycles, binary tree, perfect shuffle, or hypercube. It can be applied to approximate the transcendental numbers, such as ande, inO(logm) time by usingO(m/logm) processors for a result withm-digit precision. We also use it to costoptimally solve the second-order linear recurrence, the polynomial evaluation, the recurrence of vector norm, the general class of recurrence equation defined by Kogge and Stone (1973), and the generalmth order linear recurrence. It is easy to implement because there are only some matrix multiplications and a division operation involved.This work was supported in part by National Science Council of the Republic of China under Contract NSC 77-0408-E002-09.     

A new scheme for the deterministic simulation of PRAMs in VLSI

A deterministic scheme for the simulation of (n, m)-PRAM computation is devised. Each PRAM step is simulated on a bounded degree network consisting of a mesh-of-trees (MT) of siden. The memory is subdivided inn modules, each local to a PRAM processor. The roots of the MT contain these processors and the memory modules, while the otherO(n ²) nodes have the mere capabilities of packet switchers and one-bit comparators. The simulation algorithm makes a crucial use of pipelining on the MT, and attains a time complexity ofO(log² n/log logn). The best previous time bound wasO(log² n) on a different interconnection network withn processors. While the previous simulation schemes use an intermediate MPC model, which is in turn simulated on a bounded degree network, our method performs the simulation directly with a simple algorithm.This work has been supported in part by Ministero della Pubblica Istruzione of Italy under a research grant.     

A polynomial-time algorithm for computing K-terminal residual reliability of d-trapezoid graphs

Consider a probabilistic graph G   in which the edges of E(G)$E(G)$ are perfectly reliable, but the vertices of V(G)$V(G)$ may fail with some known probabilities. Given a subset K   of V(G)$V(G)$, the K-terminal residual reliability of G is the probability that all operational vertices in K are connected to each other. This problem can be considered to be a generalization of two well-known reliability problems – the K-terminal reliability problem and the residual connectedness reliability problem.     

On m-restricted edge connectivity of undirected generalized De Bruijn graphs

An m-restricted edge cut is an edge cut of a connected graph whose removal results in components of order at least m, the minimum cardinality over all m-restricted edge cuts of a graph is its m-restricted edge connectivity. It is known that telecommunication networks with topology having larger m-restricted edge connectivity are locally more reliable for all m≤3. This work shows that if n≥7, then undirected generalized binary De Bruijn graph UB_G(2, n) is maximally m-restricted edge connected for all m≤3, where a graph G is maximally m-restricted edge connected if its m-restricted edge connectivity is equal to the minimum number of edges from any connected subgraphs S to G?S.     

Crown graphs and subdivision of ladders are odd graceful

A graph G of size q is odd graceful, if there is an injection φ from V(G) to {0, 1, 2, …, 2q?1} such that, when each edge xy is assigned the label or weight |f(x)?f(y)|, the resulting edge labels are {1, 3, 5, …, 2q?1}. This definition was introduced in 1991 by Gnanajothi [3], who proved that the graphs obtained by joining a single pendant edge to each vertex of C _n are odd graceful, if n is even. In this paper, we generalize Gnanajothi's result on cycles by showing that the graphs obtained by joining m pendant edges to each vertex of C _n are odd graceful if n is even. We also prove that the subdivision of ladders S(L _n ) (the graphs obtained by subdividing every edge of L _n exactly once) is odd graceful.     

Fast Parallel Reordering and Isomorphism Testing of k -Trees

In this paper two problems on the class of k -trees, a subclass of the class of chordal graphs, are considered: the fast reordering problem and the isomorphism problem. An O(log ² n) time parallel algorithm for the fast reordering problem is described that uses O(nk(n-k)/\kern -1ptlog n) processors on a CRCW PRAM proving membership in the class NC for fixed k . An O(nk(k+1)!) time sequential algorithm for the isomorphism problem is obtained representing an improvement over the O(n ² k(k+1)!) algorithm of Sekharan (the second author) [10]. A parallel version of this sequential algorithm is presented that runs in O(log ² n) time using O((nk((k+1)!+n-k))/log n) processors improving on a parallel algorithm of Sekharan for the isomorphism problem [10]. Both the sequential and parallel algorithms use a concept introduced in this paper called the kernel of a k -tree.     

Smallest Bipartite Bridge-Connectivity Augmentation

This paper addresses two augmentation problems related to bipartite graphs. The first, a fundamental graph-theoretical problem, is how to add a set of edges with the smallest possible cardinality so that the resulting graph is 2-edge-connected, i.e., bridge-connected, and still bipartite. The second problem, which arises naturally from research on the security of statistical data, is how to add edges so that the resulting graph is simple and does not contain any bridges. In both cases, after adding edges, the graph can be either a simple graph or, if necessary, a multi-graph. Our approach then determines whether or not such an augmentation is possible. We propose a number of simple linear-time algorithms to solve both problems. Given the well-known bridge-block data structure for an input graph, the algorithms run in O(log n) parallel time on an EREW PRAM using a linear number of processors, where n is the number of vertices in the input graph. We note that there is already a polynomial time algorithm that solves the first augmentation problem related to graphs with a given general partition constraint in O(n(m+nlog n)log n) time, where m is the number of distinct edges in the input graph. We are unaware of any results for the second problem. H.-W. Wei, W.-C. Lu and T.-s. Hsu research supported in part by NSC of Taiwan Grants 94-2213-E-001-014, 95-2221-E-001-004 and 96-2221-E-001-004.     

On circular-L(2, 1)-labellings of products of graphs

Let m, j and k be positive integers. An m-circular-L(j, k)-labelling of a graph G is an assignment f from { 0, 1,?…?, m?1} to the vertices of G such that, for any two vertices u and v, |f(u)?f(v)|_m≥j if uv∈E(G), and |f(u)?f(v)|_m≥k if d_G(u, v)=2, where |a|_m=min{a, m?a}. The minimum m such that G has an m-circular-L(j, k)-labelling is called the circular-L(j, k)-labelling number of G. This paper determines the circular-L(2, 1)-labelling numbers of the direct product of a path and a complete graph and of the Cartesian product of a path and a cycle.     

Orthogonally Drawing Cubic Graphs in Parallel

In this paper we describe a parallel algorithm that, given annvertex cubic graphGas input, outputs an orthogonal drawing ofGwithO(n) bends,O(n) maximum edge length, andO(n²) area inO(log n) time using a CRCW PRAM withnprocessors. We give two slight variants of the algorithm. The first generates a drawing in which each edge has at most 2 bends; the total number of bends and the area are bounded byn+3 and [formula], respectively. The second optimizes the number of bends per edge (at most one) even if the values of the other functions are slightly worst. Despite its nonoptimality, this parallel algorithm is the first dealing with nonplanar, nonbiconnected graphs. Moreover, no embedding of the graph is requested as input nor is anst-numbering (orlmc-numbering) computed.