2連結平面グラフのst-numberingの列挙アルゴリズム(理論)

• 金子 昌弘

  群馬大学工学部情報工学科

• 中野 眞一

  群馬大学工学部

書誌事項

タイトル別名

• Enumerating st-numberings of Biconnected Plane Graphs(Theory)
• 2連結平面グラフのst-numberingの列挙アルゴリズム
• 2 レンケツ ヘイメン グラフ ノ st numbering ノ レッキョ アルゴリズム

抄録

n点のグラフGとGの2点sとtが与えられたとき,Gの各点に1,2,…,nの番号を割り当てる.次の3条件を満たす番号割り当てを,Gのst-numberingという.(i)点sに番号1を割り当てる.(ii)点tに番号nを割り当てる.(iii)s,t以外の各点は,より小さい番号を持つ点,および,より大きい番号を持つ点,とそれぞれ隣接する.2連結平面グラフGとGの外面上の2点sとtが与えられたとき,全てのst-numberingを,重複も抜けもなく,高速に列挙するアルゴリズムを与える.

収録刊行物

• 日本応用数理学会論文誌

  日本応用数理学会論文誌 20 (1), 33-44, 2010

  一般社団法人 日本応用数理学会

詳細情報

• CRID: 1390282680744233088
• NII論文ID: 110007580789
• NII書誌ID: AN10367166
• ISSN: 09172246
• ISSN: 24240982
• DOI: 10.11540/jsiamt.20.1_33
• NDL書誌ID: 10655346
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I10655346
• 本文言語コード: ja
• データソース種別:
  • JaLC
  • NDL
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可