著者

岩間 一雄 Lingas Andrzej 沖田 正樹

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.105, no.499, pp.49-55, 2005-12-15

参考文献数

17

---

木t-スパナーとは, グラフGの全域木でその伸長度がt以内(2つの頂点間の木上での距離がグラフ上での距離のt倍以内)であるものを言う. Gが木t-スパナーを持ち, 木t-1-スパナーを持たないとき, Gの伸長度がtであるという. 本稿ではグラフの伸長度を枝を追加して減少させる問題を議論する. 円グラフやグリッドグラフ等の特殊なグラフに対して最適な枝の追加アルゴリズムを与える. 一般のグラフに対しては問題は困難になるが, それでも, O(n/s')本の枝を追加して伸長度をs'にするアルゴリズムを与える.