| 講演名 | 2017-11-17 パンケーキグラフに対する独立木の構成方法 松井 大地(埼玉大), 山田 敏規(埼玉大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | $G$をグラフとする. $G$上の頂点$u$と$v$を結ぶ2本のパス$P,P'$が$u$と$v$以外に点を共有しないならば$P$と$P'$は内点非共有であると言われる. $r$をグラフ$G$上の頂点とする. また, $T_1,T_2,ldots T_k$を$G$に対する$k$個の全域木とし, 任意の$iin {1,2,ldots ,k}$と$G$上の任意の頂点$v$に対して$T_i$上の$r$と$v$を結ぶ(唯一の)パスを$P_i(v)$で表す. $G$上の任意の頂点$v$に対して$P_1(v),P_2(v),ldots ,P_k(v)$が内点非共有であるとき, $T_1,T_2,ldots T_k$は$r$を根として独立であると言われる. 小文では, $n$-パンケーキグラフに対して独立である$(n-1)$個の全域木を構成する. |
| 抄録(英) | Let $G$ be a graph, and let $P$ and $P'$ be two paths connecting vertices $u$ and $v$ on $G$. $P$ and $P'$ are said to be internally vertex-disjoint if the have no vertex in common, except $u$ and $v$. Let $r$ be a vertex in graph $G$. Let $T_1,T_2,ldots ,T_k$ be $k$ spanning trees of $G$, and let $P_i(v)$ denote the (unique) path connecting $r$ and $v$ on $T_i$ for any $iin {1,2,ldots ,k}$ and any vertex $v$ of $G$. $T_1,T_2,ldots ,T_k$ is said to be independent at root $r$ if $P_1(v),P_2(v),ldots ,P_k(v)$ are internally vertex-disjoint for any vertex $v$ of $G$. This paper constructs $n-1$ independent spanning trees of an $n$-Pancake graph. |
| キーワード(和) | 独立木 / パンケーキグラフ / 連結度 |
| キーワード(英) | Independent spanning trees / Pancake graphs / connectivity |
| 資料番号 | CAS2017-55,MSS2017-39 |
| 発行日 | 2017-11-09 (CAS, MSS) |
| 研究会情報 | |
| 研究会 | CAS / MSS / IPSJ-AL |
|---|---|
| 開催期間 | 2017/11/16(から2日開催) |
| 開催地（和） | 日立中央研究所 |
| 開催地（英） | |
| テーマ（和） | システムのモデリングと制御・検証・最適化の手法，機械学習的アプローチ及び一般 |
| テーマ（英） | |
| 委員長氏名（和） | 平木 充(ルネサス エレクトロニクス) / 名嘉村 盛和(琉球大) / 堀山 貴史(埼玉大学) |
| 委員長氏名（英） | Mitsuru Hiraki(Renesas) / Morikazu Nakamura(Univ. of Ryukyus) / Takashi Horiyama(Saitama University) |
| 副委員長氏名（和） | 岡崎 秀晃(湘南工科大) / 髙井 重昌(阪大) |
| 副委員長氏名（英） | Hideaki Okazaki(Shonan Inst. of Tech.) / Shigemasa Takai(Osaka Univ.) |
| 幹事氏名（和） | 山口 基(ルネサス エレクトロニクス) / 橘 俊宏(湘南工科大) / 豊嶋 伊知郎(東芝) / 金澤 尚史(阪大) / 岡本 吉央(電気通信大学) / 川原 純(奈良先端科学技術大学院大学) / 河村 彰星(東京大学) |
| 幹事氏名（英） | Motoi Yamaguchi(Renesas) / Toshihiro Tachibana(Shonan Inst. of Tech.) / Ichiro Toyoshima(Toshiba) / Takahumi Kanazawa(Osaka Univ.) / Yoshio Okamoto(The University of Electro-Communications) / Jun Kawahara(Nara Institute of Science and Technology) / Akitoshi Kawamura(University of Tokyo) |
| 幹事補佐氏名（和） | 中村 洋平(日立) / 金城 秀樹(沖縄大) |
| 幹事補佐氏名（英） | Yohei Nakamura(Hitachi) / Hideki Kinjo(Okinawa Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Circuits and Systems / Technical Committee on Mathematical Systems Science and its applications / Special Interest Group on Algorithms |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | パンケーキグラフに対する独立木の構成方法 |
| サブタイトル（和） | |
| タイトル（英） | Independent Spanning Trees on Pancake Graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 独立木 / Independent spanning trees |
| キーワード(2)（和/英） | パンケーキグラフ / Pancake graphs |
| キーワード(3)（和/英） | 連結度 / connectivity |
| 第 1 著者 氏名（和/英） | 松井 大地 / Daichi Matsui |
| 第 1 著者 所属（和/英） | 埼玉大学(略称：埼玉大) Saitama University(略称：Saitama Univ.) |
| 第 2 著者 氏名（和/英） | 山田 敏規 / Toshinori Yamada |
| 第 2 著者 所属（和/英） | 埼玉大学(略称：埼玉大) Saitama University(略称：Saitama Univ.) |
| 発表年月日 | 2017-11-17 |
| 資料番号 | CAS2017-55,MSS2017-39 |
| 巻番号（vol） | vol.117 |
| 号番号（no） | CAS-300,MSS-301 |
| ページ範囲 | pp.105-109(CAS), pp.105-109(MSS), |
| ページ数 | 5 |
| 発行日 | 2017-11-09 (CAS, MSS) |