✦ LIBER ✦

Efficient parallel algorithms for bipartite permutation graphs

✍ Scribed by Lin Chen; Yaacov Yesha

Publisher: John Wiley and Sons
Year: 1993
Tongue: English
Weight: 858 KB
Volume: 23
Category: Article
ISSN: 0028-3045
DOI: 10.1002/net.3230230105

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In this paper, we further study the properties of bipartite permutation graphs. We give first efficient parallel algorithms for several problems on bipartite permutation graphs. These problems include transforming a bipartite graph into a strongly ordered one if it is also a permutation graph; testing isomorphism; finding a Hamiltonian path/cycle; solving a variant of the crossing number problem; and others. All these problems can be solved in O(log^2^n) time with O(n^3^) processors on a Common CRCW PRAM. We also show that the minimum fill‐in problem for bipartite permutation graphs can be solved efficiently by a randomized parallel algorithm. © 1993 by John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

Efficient Parallel Algorithms for Permut

Efficient Parallel Algorithms for Permutation Graphs

✍ K. Arvind; V. Kamakoti; C.P. Rangan 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 641 KB

In this paper, we present optimal \(O(\log n)\) time, \(O(n / \log n)\) processor EREW PRAM parallel algorithms for finding the connected components, cut vertices, and bridges of a permutation graph. We also present an \(O(\log n)\) time, \(O(n)\) processor, CREW PRAM model parallel algorithm for fi

Some Efficient Algorithms for Permutatio

Some Efficient Algorithms for Permutation Graphs

✍ O.H. Ibarra; Q. Zheng 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 685 KB

An Optimal Shortest Path Parallel Algori

An Optimal Shortest Path Parallel Algorithm for Permutation Graphs

✍ O.H. Ibarra; Q. Zheng 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 512 KB

We present an optimal parallel algorithm for the single-source shortest path problem for permutation graphs. The algorithm runs in \(O(\log n)\) time using \(O(n / \log n)\) processors on an EREW PRAM. As an application, we show that a minimum connected dominating set in a permutation graph can be f

Efficient Sequential and Parallel Algori

Efficient Sequential and Parallel Algorithms for Maximal Bipartite Sets

✍ D. Pearson; V.V. Vazirani 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 344 KB

A maximal bipartite set (MBS) in an undirected graph \(G=(V, E)\) is a maximal collection of vertices \(B \subseteq V\) whose induced subgraph is bipartite. In this paper we present efficient sequential (linear time) and parallel (NC) algorithms for constructing an MBS. 1.1993 Acatemic Press, Inc

Solving the shortest-paths problem on bi

Solving the shortest-paths problem on bipartite permutation graphs efficiently

✍ Lin Chen 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 498 KB

Efficient Parallel Algorithms for Graphs

Efficient Parallel Algorithms for Graphs of Bounded Tree-Width

✍ Jens Lagergren 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 236 KB

We present an efficient parallel algorithm for the tree-decomposition problem Ž 3 . Ž. for fixed width w. The algorithm runs in time O O log n and uses O O n processors on an ARBITRARY CRCW PRAM. The sequential complexity of our tree-decom-Ž 2 . position algorithm is O O n log n . The tree-decomposi