Loading...
Please wait, while we are loading the content...
Similar Documents
Parallel algorithms for the hamiltonian cycle and hamiltonian path problems in semicomplete bipartite digraphs (1998).
| Content Provider | CiteSeerX |
|---|---|
| Author | Bang-Jensen, Jørgen Haddad, Mohammed El Manoussakis, Yannis Przytycka, Teresa M. |
| Abstract | We give an O(log 4 n)-time O(n 2 )-processor CRCW PRAM algorithm to find a hamiltonian cycle in a strong semicomplete bipartite digraph, B, provided that a factor of B (i.e. a collection of vertex disjoint cycles covering the vertex set of B) is computed in a preprocessing step. The factor is found (if it exists) using a bipartite matching algorithm, hence placing the whole algorithm in the class Random-NC. We show that any parallel algorithm which can check the existence of a hamiltonian cycle in a strong semicomplete bipartite digraph in time O(r(n)) using p(n) processors can be used to check the existence of a perfect matching in a bipartite graph in time O(r(n) + n 2 =p(n)) using p(n) processors. Hence, our problem belongs to the class NC if and only if perfect matching in bipartite graphs belongs to NC. We also consider the problem of finding a hamiltonian path in a semicomplete bipartite digraph. 1 Introduction A semicomplete digraph is a digraph with no pair of non-ad... |
| File Format | |
| Publisher Date | 1998-01-01 |
| Access Restriction | Open |
| Subject Keyword | Hamiltonian Cycle Semicomplete Bipartite Digraph Parallel Algorithm Hamiltonian Path Problem Perfect Matching Strong Semicomplete Bipartite Digraph Introduction Semicomplete Digraph Class Nc Bipartite Graph Belongs Whole Algorithm Class Random-nc Vertex Disjoint Cycle Processor Crcw Pram Algorithm Bipartite Graph Hamiltonian Path Vertex Set Preprocessing Step |
| Content Type | Text |
