文献

J-GLOBAL ID：201002253613543323   整理番号：10A0658891

外平面グラフのスパンニング木輻輳

Spanning tree congestion of k-outerplanar graphs

著者 (4件)： BODLAENDER Hans L. (Utrecht Univ., Utrecht, NLD) ,  KOZAWA Kyohei (Electric Power Dev. Co., Ltd., Tokyo, JPN) ,  MATSUSHIMA Takayoshi (Gunma Univ., Gunma, JPN) ,  OTACHI Yota (Tohoku Univ., Sendai, JPN)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 110  号： 37(COMP2010 10-14)  ページ： 43-46  発行年： 2010年05月12日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： k外平面グラフのスパンニング木輻輳について調べた。1987年に,Simonson[Math.Syst.Theroy 20(1987)235-252]は,各k平面外グラフはその最大次数の高々k倍でスパンニング木輻輳を持つことを予想した。本論文ではこの予想を肯定的に解決した。ここではまた,平面外グラフのスパンニング木輻輳が線形時間で決定可能になることを示した。(翻訳著者抄録)

シソーラス用語： *スパンニング木 ,  無次元数 ,  集中化 ,  問題解決 ,  予測 ,  *計算量 ,  アルゴリズム ,  グラフ理論
準シソーラス用語： スパンニング木輻輳 ,  *外平面グラフ ,  次数 ,  線形時間アルゴリズム ,  直並列グラフ ,  予想

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

引用文献 (15件)：

• AGNARSSON, G. On colorings of squares of outerplanar graphs. Proc. SODA 2004. 2004, 244-253
• BODLAENDER, H. L. A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. 1998, 209, 1-45
• CAI, L. Tree spanners. SIAM J. Discrete Math. 1995, 8, 359-387
• CASTEJON, A. Minimum congestion spanning trees of grids and discrete toruses. Discuss. Math. Graph Theory. 2009, 29, 511-519
• FEKETE, S. P. Tree spanners in planar graphs. Discrete Appl. Math. 2001, 108, 85-103

タイトルに関連する用語 (3件)： 平面グラフ ,  スパンニング木 ,  輻輳