Efficient Parallel Algorithms on Proper Circular Arc Graphs (Special Issue on Architectures, Algorithms and Networks for Massively Parallel Computing)

スポンサーリンク

概要

• 論文の詳細を見る

• Efficient parallel algorithms for several problems on proper circular arc graphs are presented in this paper. These problems include finding a maximum matching, partitioning into a minimum number of induced subgraphs each of which has a Hamiltonian cycle (path), partitioning into induced subgraphs each of which has a Hamiltonian cycle (path) with at least k vertices for a given k, and adding a minimum number of edges to make the graph contain a Hamiltonian cycle (path). It is shown here that the above problems can all be solved in logarithmic time with a linear number of EREW PRAM processors, or in constant time with a linear number of BSR processors. A more important part of this work is perhaps the extension of basic BSR to allow simultaneous multiple BROADCAST instructions.

• 社団法人電子情報通信学会の論文
• 1996-08-25

著者

• Chen Lin

  米国

• Chen L

  Huazhong Univ. Sci. & Tech. Chn

• AKL Selim

  Department of Computing and Information Science, Queen's University

• CHEN Lin

  Fundamental Research Laboratory

• Akl Selim

  Department Of Computing And Information Science Queen's University

関連論文

• The involvement of neutrophils in the resistance to Leishmania major infection in susceptible but not in resistant mice
• Molecular cloning and expression of a Schistosoma japonicum tegumental membrane-associated antigen from Japanese strain
• Efficient Parallel Algorithms on Proper Circular Arc Graphs (Special Issue on Architectures, Algorithms and Networks for Massively Parallel Computing)

スポンサーリンク