Constant-Time Algorithms for Interval Graph Problems on Reconfigurable Meshes (Extended Abstract)

スポンサーリンク

概要

• 論文の詳細を見る

• 本文では,インターバルグラフにおけるdomatic partition problemと彩色問題の2つの問題を可変構造メッシュ上で並列に解く定数時間のアルゴリズムを与える.これらの問題を解く定数時間のアルゴリズムは理想的なCRCW-PRAMを用いたものでさえも今までは得られていない.本文では2つのアルゴリズムを2次元の2n×2nの可変構造メッシュ上で設計する.ここで,nはインターバルグラフの頂点数である.可変構造メッシュはプロセッサの配列と格子状の可変構造のバスからなり,並列計算の実際的なモデルである.

• 一般社団法人情報処理学会の論文
• 1995-07-20

著者

• Park K

  Seoul National Univ. Seoul Kor

• Park Kunsoo

  School Of Computer Science And Engineering Seoul National University

• Cho Y

  School Of Computer Science And Engineering Seoul National University

• Chung Yoojin

  Department of Computer Engineering Seoul National University

• Park Kunsoo

  Department of Computer Engineering Seoul National University

• Cho Yookun

  Department of Computer Engineering Seoul National University

関連論文

• Fast Computation of Rank and Select Functions for Succinct Representation
• Performance Estimation of an HDD for Multimedia Service Using an HDD Simulator
• Finish Time Predictability of Earliest Deadline Zero Laxity Algorithm for Multiprocessor Real-Time Systems(System Programs)
• Comparison of Deadline-Based Scheduling Algorithms for Periodic Real-Time Tasks on Multiprocessor(System Programs)
• Constant-Time Algorithms for Interval Graph Problems on Reconfigurable Meshes (Extended Abstract)
• Efficient Arithmetic in Optimal Extension Fields Using Simultaneous Multiplication
• Efficient Implementation of NTRU Cryptosystem Using Sliding Window Methods

スポンサーリンク