| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2018-09-18 15:20 非同型な2端子直並列グラフの列挙とランダムサンプリング 伝住周平（東大）・堀山貴史（埼玉大）・栗田和宏（北大）・中畑 裕（奈良先端大）・鈴木浩史（北大）・○和佐州洋（NII）・山崎一明（北陸先端大）  COMP2018-17 |
|
| 抄録 | （和） | 2端子直並列グラフとは，2つの頂点とそれらをつなぐ1つの辺からなるグラフに対して，次の2種類の操作を繰り返し適用することで得られる多重グラフのことをいう：($S$操作) 2つのグラフを直列に接続する，($P$操作) 2つのグラフを並列に接続する．本稿では，自然数$n$が与えられた時，辺数が$n$となる2端子直並列グラフの全てからなる集合を求める漸化式を与える．さらに，与えた漸化式に基づいて，全ての解を実際に出力するアルゴリズムおよびランダムサンプリングアルゴリズムの構築についても議論する．いずれのアルゴリズムも，出力する解1つあたり多項式時間および多項式領域を必要とするアルゴリズムである． |
| （英） | A graph $G$ is a two-terminal series-parallel graph if (1) $G$ consists of two vertices and an edge between them or (2) $G$ is generated by the following two operations: ($S$ operation) connecting a pair of two-terminal series-parallel graphs in series, and ($P$ operation) connecting a pair of two-terminal series-parallel graphs in parallel. In this paper, given a natural number $n$, we show a recurrence formula for obtaining the set of two-terminal series-parallel graphs with $n$ edges. Moreover, by using the formula, we develop algorithms for enumerating solutions and outputting a two-terminal series-parallel graph randomly. Both algorithms run in polynomial time and space per solution. | |
| キーワード | （和） | 列挙 / 2端子直並列グラフ / ランダムサンプリング / 多項式遅延 / / / / |
| （英） | Enumeration / two-terminal series-parallel graphs / random sampling / polynomial delay / / / / | |
| 文献情報 | 信学技報, vol. 118, no. 216, COMP2018-17, pp. 55-62, 2018年9月. | |
| 資料番号 | COMP2018-17 | |
| 発行日 | 2018-09-11 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2018-17 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2018-09-18 - 2018-09-18 |
| 開催地（和） | 九州工業大学（飯塚キャンパス） |
| 開催地（英） | Kyusyu Institute of Technology |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2018-09-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | 非同型な2端子直並列グラフの列挙とランダムサンプリング |
| サブタイトル（和） | |
| タイトル（英） | Enumeration and Random Sampling of Nonisomorphic Two-Terminal Series-Parallel Graphs |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 列挙 / Enumeration |
| キーワード(2)（和/英） | 2端子直並列グラフ / two-terminal series-parallel graphs |
| キーワード(3)（和/英） | ランダムサンプリング / random sampling |
| キーワード(4)（和/英） | 多項式遅延 / polynomial delay |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 伝住 周平 / Shuhei Denzumi / デンズミ シュウヘイ |
| 第1著者 所属（和/英） | 東京大学 (略称： 東大) The University of Tokyo (略称： UTokyo) |
| 第2著者 氏名（和/英/ヨミ） | 堀山 貴史 / Takashi Horiyama / ホリヤマ タカシ |
| 第2著者 所属（和/英） | 埼玉大学 (略称： 埼玉大) Saitama University (略称： Saitama Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 栗田 和宏 / Kazuhiro Kurita / クリタ カズヒロ |
| 第3著者 所属（和/英） | 北海道大学 (略称： 北大) Hokkaido University (略称： Hokudai) |
| 第4著者 氏名（和/英/ヨミ） | 中畑 裕 / Yu Nakahata / ナカハタ ユウ |
| 第4著者 所属（和/英） | 奈良先端科学技術大学院大学 (略称： 奈良先端大) Nara Institute of Science and Technology (略称： NAIST) |
| 第5著者 氏名（和/英/ヨミ） | 鈴木 浩史 / Hirofumi Suzuki / スズキ ヒロフミ |
| 第5著者 所属（和/英） | 北海道大学 (略称： 北大) Hokkaido University (略称： Hokudai) |
| 第6著者 氏名（和/英/ヨミ） | 和佐 州洋 / Kunihiro Wasa / |
| 第6著者 所属（和/英） | 国立情報学研究所 (略称： NII) National Institute of Informatics (略称： NII) |
| 第7著者 氏名（和/英/ヨミ） | 山崎 一明 / Kazuaki Yamazaki / ヤマザキ カズアキ |
| 第7著者 所属（和/英） | 北陸先端科学技術大学院大学 (略称： 北陸先端大) Japan Advanced Institute of Science and Technology (略称： JAIST) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第6著者 |
| 発表日時 | 2018-09-18 15:20:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2018-17 |
| 巻番号（vol） | vol.118 |
| 号番号（no） | no.216 |
| ページ範囲 | pp.55-62 |
| ページ数 | 8 |
| 発行日 | 2018-09-11 (COMP) |
[研究会発表申込システムのトップページに戻る]