| 講演名 | 1993/5/27 凸多角形内の全最遠近隣を求める並列アルゴリズム 陳 慰, 増澤 利光, 都倉 信樹, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 凸多角形内の全最遠近隣を求める問題とは,凸多角形Pが与えられたとき,Pの各頂点υについて,クリッド)距離が一番遠いPの頂点を求める問題である.本研究では,この問題を解く2つの並列を提案する.一つのアルゴリズムは,任意の凸多角形について,問題をEREW PRAM上で,O(log時間,n,log nプロセッサで解く.もう一つのアルゴリズムは,unimodal凸多角形(各頂点υに対し頂点との距離関数には一回しかローカル極大値が現れない凸多角形)について,問題を(i)CRCWO(log log n)時間,n/log log nプロセッサで,(ii)EREW PRAM上で,O(log n)時間,n/log nプロCRCW PRAM上で,O(1)時間,n^1+ε>(εは任意の正定数)で解く.また, O(n log^c n)プロセッサ(cはを用いるときに,CRCW PRAM上で,unimodal凸多角形内の全最遠近隣を求める時間計算量の下界であることを証明した. |
| 抄録(英) | Let F be a family of non empty sets.A graph G is an intersection graph associated with F if its vertices can be put in a one-to-one correspondence with the elements of F,in such a way that two vertices axe adjacent in G if and only if the two corresponding sets in F have a non empty intersection. Graph G is called a rectangle-on-a-cylinder-intersection-graph if F is a set of isooriented rectangles on the side of a cylinder, F being called a rectangle-on-a-cylinder-intersection model for G. In this paper,an algorithm is presented that,given the rectangle- on-a-cylinder-intersection model F of graph G,finds a maximum clique of G in O(n^2+ne)time and O(n)space,where n is the number of vertices and e is the number of edges. |
| キーワード(和) | 全最遠近隣問題 / PRAM並列計算モデル / 最適並列アルゴリズム / 計算幾何学 |
| キーワード(英) | the all farthost neighbors problem / PRAM parallel computational models / optimal parallel algorithms / computational geometry |
| 資料番号 | COMP93-11,SS93-5 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1993/5/27(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 凸多角形内の全最遠近隣を求める並列アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Find All Farthest Neighbors in Convex Polygons in Parallel |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 全最遠近隣問題 / the all farthost neighbors problem |
| キーワード(2)（和/英） | PRAM並列計算モデル / PRAM parallel computational models |
| キーワード(3)（和/英） | 最適並列アルゴリズム / optimal parallel algorithms |
| キーワード(4)（和/英） | 計算幾何学 / computational geometry |
| 第 1 著者 氏名（和/英） | 陳 慰 / Wei Chen |
| 第 1 著者 所属（和/英） | 大阪大学基礎工学部 Faculty of Engineering Science,Osaka University |
| 第 2 著者 氏名（和/英） | 増澤 利光 / Yoshimitsu Masuzawa |
| 第 2 著者 所属（和/英） | 大阪大学基礎工学部 Faculty of Engineering Science,Osaka University |
| 第 3 著者 氏名（和/英） | 都倉 信樹 / Nobuki Tokura |
| 第 3 著者 所属（和/英） | 大阪大学基礎工学部 Faculty of Engineering Science,Osaka University |
| 発表年月日 | 1993/5/27 |
| 資料番号 | COMP93-11,SS93-5 |
| 巻番号（vol） | vol.93 |
| 号番号（no） | 81 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |