Spanning tree congestion of k-outerplanar graphs (コンピュテーション)

スポンサーリンク

概要

• 論文の詳細を見る

• We investigate the spanning tree congestion of k-outerplanar graphs. In 1987, Simonson [Math. Syst. Theory 20(1987) 235-252] conjectured that every k-outerplanar graph has spanning tree congestion at most k times its maximum degree. We settle this conjecture affirmatively. We also show that the spanning tree congestion of outerplanar graphs can be determined in linear time.

• 社団法人電子情報通信学会の論文
• 2010-05-12

著者

• Otachi Yota

  Graduate School Of Information Sciences Tohoku University

• Bodlaender Hans

  Institute Of Information And Computing Sciences Utrecht University

• KOZAWA Kyohei

  Electric Power Development Co., Ltd.

• MATSUSHIMA Takayoshi

  Department of Computer Science, Gunma University

• Kozawa Kyohei

  Electric Power Development Co. Ltd.

• Matsushima Takayoshi

  Department Of Computer Science Gunma University

• Otachi Yota

  Tohoku Univ. Sendai Jpn

• Otachi Yota

  Graduate School Of Information Science Tohoku University

関連論文

• Bipartite powers of interval bigraphs
• Enumerating All Rooted Trees Including k Leaves
• 全域木混雑度問題の計算複雑性
• Spanning tree congestion of k-outerplanar graphs (コンピュテーション)
• Reconstructing sets from distances given by graphs (コンピュテーション)
• Hardness results and an exact exponential algorithm for the spanning tree congestion problem (コンピュテーション)
• DS-1-11 An Algorithm for Optimally Locating Baselines using Quad Decomposition
• Enumerating All Rooted Trees Including k Leaves

スポンサーリンク