| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2010-01-25 13:35 根付き三角化平面的グラフの列挙 ○庄 冰冰・永持 仁（京大）  COMP2009-43 |
|
| 抄録 | （和） | すべての内面が三角形となる平面埋め込みを持つ２点連結平面的グラフで １個の点$v$と接続する２辺$e,e'$を指定したとき，これらが外面に現れる 平面埋め込みを考える． このような平面埋め込みのうち，$v$と$\{e,e'\}$を固定したグラフ同型性において 異なる埋め込みをすべて列挙する 方法を与える．提案法は，$v$に関して軸対称な埋め込みだけ，あるいは 非対称な埋め込みだけを生成することができ，１個当たりの生成時間は， 直前の出力との差分のみを出力することで定数時間ですむ． |
| （英） | A graph is called a triangulated planar graph if it admits a plane embedding in the plane such that all inner faces are triangle. In a rooted triangulated planar graph, a vertex and two edges incident to it are designated as an outer vertex and outer edges, respectively. Two plane embedding of rooted triangulated planar graphs are defined to be equivalent if they admit an isomorphism such that the designated vertices correspond each other. Given a positive integer $n$, we give an algorithm for enumerating all plane embeddings of rooted, biconnected and triangulated planar graphs with at most $n$ vertices without delivering two equivalent embeddings. The algorithm runs in constant time per each by outputting the difference from the previous output. |
|
| キーワード | （和） | 三角化平面グラフ / ２点連結 / 列挙アルゴリズム / / / / / |
| （英） | triangulated plane graphs / enumeration / biconnected / / / / / | |
| 文献情報 | 信学技報, vol. 109, no. 391, COMP2009-43, pp. 29-36, 2010年1月. | |
| 資料番号 | COMP2009-43 | |
| 発行日 | 2010-01-18 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2009-43 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2010-01-25 - 2010-01-25 |
| 開催地（和） | 九州大学西新プラザ |
| 開催地（英） | Nishijin Plaza, Kyushu University |
| テーマ（和） | 情報処理学会アルゴリズム研究会との連続開催 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2010-01-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 根付き三角化平面的グラフの列挙 |
| サブタイトル（和） | |
| タイトル（英） | Enumerating Rooted and Triangulated Planar Graphs |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 三角化平面グラフ / triangulated plane graphs |
| キーワード(2)（和/英） | ２点連結 / enumeration |
| キーワード(3)（和/英） | 列挙アルゴリズム / biconnected |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 庄 冰冰 / Bingbing Zhuang / ショウ ヒョウヒョウ |
| 第1著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 永持 仁 / Hiroshi Nagamochi / ナガモチ ヒロシ |
| 第2著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2010-01-25 13:35:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2009-43 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | no.391 |
| ページ範囲 | pp.29-36 |
| ページ数 | 8 |
| 発行日 | 2010-01-18 (COMP) |
[研究会発表申込システムのトップページに戻る]