Efficient parallel algorithms for bipartite permutation graphs
- 1 January 1993
- Vol. 23 (1) , 29-39
- https://doi.org/10.1002/net.3230230105
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 inO(log2n) time withO(n3) 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.Keywords
This publication has 14 references indexed in Scilit:
- Parallel recognition of the consecutive ones property with applicationsJournal of Algorithms, 1991
- Parallel Merge SortSIAM Journal on Computing, 1988
- Bipartite permutation graphsDiscrete Applied Mathematics, 1987
- Constructing a perfect matching is in random NCCombinatorica, 1986
- The NP-completeness column: an ongoing guideJournal of Algorithms, 1985
- A parallel matching algorithm for convex bipartite graphs and applications to schedulingJournal of Parallel and Distributed Computing, 1984
- The NP-completeness column: An ongoing guideJournal of Algorithms, 1982
- Computing the Minimum Fill-In is NP-CompleteSIAM Journal on Algebraic Discrete Methods, 1981
- Parallel Prefix ComputationJournal of the ACM, 1980
- Incidence matrices and interval graphsPacific Journal of Mathematics, 1965