Parallel algorithms for finding the connected components (CC) and a minimum spanning FOREST (MSF) of an undirected graph are presented. The primary model of computation considered is that called "shuffle-exchange network" in which each processor has its own local memory, no memory is shared, and communication among processors is done via a fixed degree network. This model is very convenient for actual realization. Both algorithms have depth of O(log2 n) while using n2 processors. Here n is the number of vertices in the graph. The algorithms are first presented for the PRAM (parallel RAM) model, which is not realizable, but much more convenient for the design and presentation of algorithms. The CC and MSF algorithms are no exceptions. The CC PRAM algorithm is a simplification of the one appearing in [17]. A modification of this algorithm yields a simple and efficient MSF algorithm. Both have depth of O(log m) and they use m processors, where m is the number of edges in the graph.

A parallel algorithm for finding Euler circuits in graphs is presented. Its depth is log |E| and it employs |E| processors. The computational model considered is the PRAM (the shared memory model).

Abstract The following problem is considered: Given an integer K, a graph G with two distinct vertices s and t, find the maximum number of disjoint paths of length K from s to t. The problem has several variants: the paths may be vertex‐disjoint or edge‐disjoint, the lengths of the paths may be equal to K or bounded by K, the graph may be undirected or directed. It is shown that except for small values of K all the problems are NP‐complete. Assuming P ≠ NP, for each problem, the largest value of K for which the problem is not NP‐complete is found. Whenever a polynomial algorithm exists, an efficient algorithm is described.

article Free Access Share on An On-Line Edge-Deletion Problem Authors: Yossi Shiloach IBM Israel Scientific Center, Technion City, Haifa, Israel and Stanford University, Stanford, California IBM Israel Scientific Center, Technion City, Haifa, Israel and Stanford University, Stanford, CaliforniaView Profile , Shimon Even Computer Science Department, Technion, Haifa, Israel and University of California, Berkeley, California Computer Science Department, Technion, Haifa, Israel and University of California, Berkeley, CaliforniaView Profile Authors Info & Claims Journal of the ACMVolume 28Issue 1Jan. 1981 pp 1–4https://doi.org/10.1145/322234.322235Published:01 January 1981Publication History 189citation1,844DownloadsMetricsTotal Citations189Total Downloads1,844Last 12 Months172Last 6 weeks27 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

article Free Access Share on A Polynomial Solution to the Undirected Two Paths Problem Author: Yossi Shiloach IBM Israel Scientific Research Center, Technion City, Haifa, Israel and Standford University, Stanford, California IBM Israel Scientific Research Center, Technion City, Haifa, Israel and Standford University, Stanford, CaliforniaView Profile Authors Info & Claims Journal of the ACMVolume 27Issue 3July 1980 pp 445–456https://doi.org/10.1145/322203.322207Published:01 July 1980Publication History 162citation1,046DownloadsMetricsTotal Citations162Total Downloads1,046Last 12 Months40Last 6 weeks4 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We present a constructive algorithm for solving systems of linear inequalities (LI) with at most two variables per inequality. The time complexity of the algorithm is $O(mn^3 I)$ on a random access machine, where m is the number of inequalities, n the number of variables, and I the size of the binary encoding of the input. The LI problem is of importance in complexity theory because it is polynomial time (Turing) equivalent to linear programming. The subclass of LI treated in this paper is of practical interest in mechanical verification systems.

Given an undirected planar graph with n vertices, we present an $O((n\log n)^2 )$ algorithm which finds the minimum cuts between all the pairs of vertices.

We present a constructive algorithm for solving systems of linear inequalities (LI) with at most two variables per inequality. The algorithm is polynomial in the size of the input. The LI problem is of importance in complexity theory since it is polynomial time (Turing) equivalent to linear programming. The subclass of LI treated in this paper is also of practical interest in mechanical verification systems, and we believe that the ideas presented can be extended to the general LI problem.

Efficient algorithms for finding maximum flow in planar networks are presented. These algorithms take advantage of the planarity and are superior to the most efficient algorithms to date. If the source and the terminal are on the same face, an algorithm of Berge is improved and its time complexity is reduced to $O(n\log n)$. In the general case, for a given $D > 0$ a flow of value D is found if one exists; otherwise, it is indicated that no such flow exists. This algorithm requires $O(n^2 \log n)$ time. If the network is undirected a minimum cut may be found in $O(n^2 \log n)$ time. All algorithms require $O(n)$ space.

The minimum linear arrangement problem is a special case of more general placement problems which are discussed in Hanan and Kurtzberg [5] and might occur in solving wiring problems as well as many other placement problems. It is also a special case of the quadratic assignment problem [5] and has a lot in common with job sequencing problems (Adolphson and Hu [1, § 4]). The minimum linear arrangement problem for general undirected graphs is $NP$ complete as shown in Garey et al. [2]. The corresponding problem for acyclic directed graphs is also $NP$ complete (Evan and Shiloach [4]). D. Adolphson and T. C. Hu [1] solved the problem for rooted trees by an $O(n\log n)$ algorithm. In this paper we solve the problem for undirected trees by an $O(n^{2.2} )$ algorithm.

Given an undirected 0–1 flow network with n vertices and m edges, we present an $O(n^2 (m + n))$ algorithm which generates all $\begin{pmatrix} n \\ 2 \end{pmatrix}$ maximal flows between all the pairs of vertices. Since $O(n^2 (m + n))$ is also the size of the output, this algorithm is optimal up to a constant factor.

article Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph Share on Authors: Y. Shiloach Weizmann Institute of Science, Rehovot, Israel and Computer Science Department, Stanford University, Stanford, CA Weizmann Institute of Science, Rehovot, Israel and Computer Science Department, Stanford University, Stanford, CAView Profile , Y. Perl Department of Mathematics and Computer Science, Bar-Ilan University, Ramat-Gan, Israel Department of Mathematics and Computer Science, Bar-Ilan University, Ramat-Gan, IsraelView Profile Authors Info & Claims Journal of the ACMVolume 25Issue 1Jan. 1978 pp 1–9https://doi.org/10.1145/322047.322048Published:01 January 1978 98citation1,915DownloadsMetricsTotal Citations98Total Downloads1,915Last 12 Months47Last 6 weeks5 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 SiteGet Access

Abstract The problems of layout of printed circuits and large scale integrated chips are very complex and are therefore usually approached by heuristic methods. This paper presents a more analytic approach to an elementary subset of these problems, using combinatorial and graphtheoretic arguments.