| Presentation | 2017-11-17 Independent Spanning Trees on Pancake Graphs Daichi Matsui, Toshinori Yamada, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Independent spanning trees / Pancake graphs / connectivity |
| Paper # | CAS2017-55,MSS2017-39 |
| Date of Issue | 2017-11-09 (CAS, MSS) |
| Conference Information | |
| Committee | CAS / MSS / IPSJ-AL |
|---|---|
| Conference Date | 2017/11/16(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Mitsuru Hiraki(Renesas) / Morikazu Nakamura(Univ. of Ryukyus) / Takashi Horiyama(Saitama University) |
| Vice Chair | Hideaki Okazaki(Shonan Inst. of Tech.) / Shigemasa Takai(Osaka Univ.) |
| Secretary | Hideaki Okazaki(Renesas) / Shigemasa Takai(Shonan Inst. of Tech.) / (Toshiba) |
| Assistant | Yohei Nakamura(Hitachi) / Hideki Kinjo(Okinawa Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Circuits and Systems / Technical Committee on Mathematical Systems Science and its applications / Special Interest Group on Algorithms |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Independent Spanning Trees on Pancake Graphs |
| Sub Title (in English) | |
| Keyword(1) | Independent spanning trees |
| Keyword(2) | Pancake graphs |
| Keyword(3) | connectivity |
| 1st Author's Name | Daichi Matsui |
| 1st Author's Affiliation | Saitama University(Saitama Univ.) |
| 2nd Author's Name | Toshinori Yamada |
| 2nd Author's Affiliation | Saitama University(Saitama Univ.) |
| Date | 2017-11-17 |
| Paper # | CAS2017-55,MSS2017-39 |
| Volume (vol) | vol.117 |
| Number (no) | CAS-300,MSS-301 |
| Page | pp.pp.105-109(CAS), pp.105-109(MSS), |
| #Pages | 5 |
| Date of Issue | 2017-11-09 (CAS, MSS) |