WEKO3
アイテム
Constant - Time Algorithms for Interval Graph Problems on Reconfigurable Meshes (Extended Abstract)
https://ipsj.ixsq.nii.ac.jp/records/32339
https://ipsj.ixsq.nii.ac.jp/records/32339468d166b-318e-4926-a615-93cc212be2e6
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL95046007.pdf (675.8 kB)
|
Copyright (c) 1995 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1995-07-20 | |||||||
| タイトル | ||||||||
| タイトル | Constant - Time Algorithms for Interval Graph Problems on Reconfigurable Meshes (Extended Abstract) | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Constant - Time Algorithms for Interval Graph Problems on Reconfigurable Meshes (Extended Abstract) | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| Department of Computer Engineering Seoul National University | ||||||||
| 著者所属 | ||||||||
| Department of Computer Engineering Seoul National University | ||||||||
| 著者所属 | ||||||||
| Department of Computer Engineering Seoul National University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Engineering Seoul National University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Engineering Seoul National University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Engineering Seoul National University | ||||||||
| 著者名 |
Yoojin, Chung
× Yoojin, Chung
|
|||||||
| 著者名(英) |
Yoojin, Chung
× Yoojin, Chung
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 本文では，インターバルグラフにおけるdomatic partition problemと彩色問題の2つの問題を可変構造メッシュ上で並列に解く定数時間のアルゴリズムを与える．これらの問題を解く定数時間のアルゴリズムは理想的なCRCW?PRAMを用いたものでさえも今までは得られていない．本文では2つのアルゴリズムを2次元の2n×2nの可変構造メッシュ上で設計する．ここで，nはインターバルグラフの頂点数である．可変構造メッシュはプロセッサの配列と格子状の可変構造のバスからなり，並列計算の実際的なモデルである． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | In this paper, we present O(1) time algorithms to solve two problems in interval graphs on the reconfigurable mesh. The two problems are the domatic partition problem and the minimum coloring problem in interval graphs. These problems have not been solved in O(1) time before, even on the idealistic CRCW PRAM model. These two algorithms are designed on a two-dimensional 2n×2n reconfigurable mesh, where n is the number of vertices (intervals) in an interval graph. The reconfigurable mesh consists of an array of processors and a reconfigurable bus system in a grid shape, and it is a practical model of parallel computation. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 1995, 号 71(1995-AL-046), p. 49-56, 発行日 1995-07-20 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
