| Item type |
SIG Technical Reports(1) |
| 公開日 |
2016-02-28 |
| タイトル |
|
|
タイトル |
直並列グラフの列挙 |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Enumeration of All Series-Parallel Graphs |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
北陸先端科学技術大学院大学 |
| 著者所属 |
|
|
|
北陸先端科学技術大学院大学 |
| 著者名 |
藤井, 淳
上原, 隆平
|
| 著者名(英) |
Atsushi, Fujii
Ryuhei, Uehara
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
電気・電子回路の配線問題を扱う手法の一つに，直並列グラフを回路のモデルとして用いる方法がある．このとき回路の規模を指定した場合，実現可能な回路モデルを全て知ることは有用である．直並列グラフの辺数を入力サイズとするアルゴリズムは既に知られているが，実際の配線を考慮すると，各端子間の多重配線は適当ではなく，頂点数入力に対するアルゴリズムは未だに考案されていない．本稿では，既存アルゴリズムを元に 2-tree の概念を導入し，頂点数入力による多重辺を含まない直並列グラフ列挙アルゴリズムを提案する． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
There is no algorithm that enumerates all series-parallel graphs by putting the number of vertices as a size of the seres-parallel graph. In addition, the multiple trace between arbitrary 2 terminals in an electric circuit is not considered desirable. So the algorithm that enumerates simple series-parallel graphs should be proposed. We give an algorithm to enumerate all series-parallel graphs n vertices and no multi-edge without repetition. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2016-AL-157,
号 9,
p. 1-7,
発行日 2016-02-28
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL16157009.pdf (1.1 MB)
