| 講演名 | 1993/5/27 円筒上長方形交グラフの最大クリークを求めるアルゴリズム 木津 隆史, 荒木 俊郎, 柏原 敏伸, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 円筒の側面上に,その辺が円筒の上面,下面と平行または垂直になるように張り付けられた長方形群Fを考える.長方形R∈FとグラフG(V,E)の頂点υ∈Vの間に1対1対応で存在し,2つの長方形が交わりを持つときかつそのときのみ対応する2頂点間に無向辺が存在するグラフのことを円筒上長方形交グラフと呼び,Fをそのグラフの円筒上長方形交モデルと呼ぶ.本論文では,円筒上長方形交モデルFが与えられたとき,それに対応する円筒上長方形交グラフの最大クリークを時間計算量O(n^2+ne),空間計算量O(n)(nは頂点数,eは辺の本数)で求めるアルゴリズムを与える. |
| 抄録(英) | 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. |
| キーワード(和) | 交グラフ / 円弧グラフ / 円筒上長方形交グラフ / 最大クリーク |
| キーワード(英) | intersection graph / circular-arc graph / rectangle-on-a- cylinder-intersection graph / maximum clique |
| 資料番号 | COMP93-10,SS93-4 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1993/5/27(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 円筒上長方形交グラフの最大クリークを求めるアルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | An algorithm for maximum clique of intersection graph of isooriented rectangles on a cylinder |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 交グラフ / intersection graph |
| キーワード(2)（和/英） | 円弧グラフ / circular-arc graph |
| キーワード(3)（和/英） | 円筒上長方形交グラフ / rectangle-on-a- cylinder-intersection graph |
| キーワード(4)（和/英） | 最大クリーク / maximum clique |
| 第 1 著者 氏名（和/英） | 木津 隆史 / Takashi Kizu |
| 第 1 著者 所属（和/英） | 大阪大学基礎工学部情報工学科 Department of Information and Computer Sciences,Faculty of Engineering Science Osaka University |
| 第 2 著者 氏名（和/英） | 荒木 俊郎 / Toshiro Araki |
| 第 2 著者 所属（和/英） | 大阪大学基礎工学部情報工学科 Department of Information and Computer Sciences,Faculty of Engineering Science Osaka University |
| 第 3 著者 氏名（和/英） | 柏原 敏伸 / Toshinobu Kashiwabara |
| 第 3 著者 所属（和/英） | 大阪大学基礎工学部情報工学科 Department of Information and Computer Sciences,Faculty of Engineering Science Osaka University |
| 発表年月日 | 1993/5/27 |
| 資料番号 | COMP93-10,SS93-4 |
| 巻番号（vol） | vol.93 |
| 号番号（no） | 81 |
| ページ範囲 | pp.- |
| ページ数 | 7 |
| 発行日 | |