Premium
Efficient parallel algorithms for bipartite permutation graphs
Author(s) -
Chen Lin,
Yesha Yaacov
Publication year - 1993
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230230105
Subject(s) - bipartite graph , combinatorics , hamiltonian path problem , permutation graph , mathematics , complete bipartite graph , discrete mathematics , hamiltonian path , permutation (music) , cograph , graph isomorphism , pathwidth , algorithm , graph , line graph , physics , acoustics
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.