講演抄録/キーワード |
講演名 |
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 |