| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2024-03-14 16:30 漸化式による全域木多面体の体積の表現とその計算に関する考察 ○安藤 映（専修大）  COMP2023-35 |
|
| 抄録 | （和） | 本稿では全域木多面体の体積を計算する方法について考える． 木幅が定数$k$によって抑えられているグラフ$G=(V,E)$において，全域木多面体の体積は グラフの規模の多項式時間で計算できる． このために本稿ではまず全域森多面体の体積が，$O(|V|+|E|)$回の定積分を含む 漸化式の形で表現できることを示し，その後で木幅定数のグラフに対するアルゴリズム を示す．そして全域木多面体の体積は全域森多面体の体積のアルゴリズムを少しだけ 拡張したもので求められることを示し，全域森多面体に対しては $O((k+1)^2!(k+1)^4n^{k+3})$で，全域木多面体に対しては$O((k+2)^2!(k+2)^4n^{k+3})$ 時間でアルゴリズムの実行が完了することを示す． |
| （英） | In this paper, we consider the volume of the spanning tree polytope and we can compute its volume exactly in polynomial time if the treewidth of $G$ is bounded by a constant. We show that the volume of the spanning forest polytope can be computed by repeating definite integrals $O(|V|+|E|)$ times. Then, we show an algorithm for computing the volume of the spanning forest polytope. We at last show the computation of the the spanning tree polytope's volume by considering additional condition, and show that our algorithms compute the volume of the spanning forest polytope and the volume of the spanning tree polytope in $O((k+1)^2!(k+1)^4n^{k+3})$ time and $O((k+2)^2!(k+2)^4n^{k+3})$ time, |
|
| キーワード | （和） | 高次元体積 / 全域木多面体 / 木幅 / / / / / |
| （英） | high dimensional volume / spanning tree polytope / treewidth / / / / / | |
| 文献情報 | 信学技報, vol. 123, no. 444, COMP2023-35, pp. 42-49, 2024年3月. | |
| 資料番号 | COMP2023-35 | |
| 発行日 | 2024-03-07 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2023-35 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2024-03-14 - 2024-03-14 |
| 開催地（和） | 電気通信大学 |
| 開催地（英） | The University of Electro-Communications |
| テーマ（和） | 理論計算機科学，一般 |
| テーマ（英） | Theoretical Computer Science, etc |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2024-03-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 漸化式による全域木多面体の体積の表現とその計算に関する考察 |
| サブタイトル（和） | |
| タイトル（英） | A consideration on the spannig polytope volume using the recurrence representation and its computation |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 高次元体積 / high dimensional volume |
| キーワード(2)（和/英） | 全域木多面体 / spanning tree polytope |
| キーワード(3)（和/英） | 木幅 / treewidth |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 安藤 映 / Ei Ando / アンドウ エイ |
| 第1著者 所属（和/英） | 専修大学 (略称： 専修大) Senshu Univeristy (略称： Senshu Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2024-03-14 16:30:00 |
| 発表時間 | 30分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2023-35 |
| 巻番号（vol） | vol.123 |
| 号番号（no） | no.444 |
| ページ範囲 | pp.42-49 |
| ページ数 | 8 |
| 発行日 | 2024-03-07 (COMP) |
[研究会発表申込システムのトップページに戻る]