Efficient parallel algorithms for bipartite permutation graphs | Zendy

Chen Lin | Zendy; Yesha Yaacov | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research