Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem

• Okamoto, Yoshio

• Otachi, Yota

• Uehara, Ryuhei

• Uno, Takeaki

Abstract

Spanning tree congestion is a relatively new graph parameter, whichhas been studied intensively. This paper studies the complexity of the problemto determine the spanning tree congestion for non-sparse graph classes, while itwas investigated for some sparse graph classes before. We prove that the problemis NP-hard even for chain graphs and split graphs. To cope with the hardnessof the problem, we present a fast (exponential-time) exact algorithm that runs inO ^∗(2^n) time, where n denotes the number of vertices. Additionally, we providea constant-factor approximation algorithm for cographs, and a linear-time algorithmfor chordal cographs.

8th Annual Conference on Theory and Applications of Medels of Computation, TAMC 2011, Tokyo, Japan, May 23-25, 2011.

identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/9861

Journal

• Lecture Notes in Computer Science

  Lecture Notes in Computer Science 6648/2011 452-462, 2011-04-27

  Springer

Keywords

• Spanning tree congestion
• chain graph
• split graph
• cograph
• computational complexity

Details

• CRID: 1050282812515010304
• NII Article ID: 110008601836
• NII Article ID: 120003752202
• NII Article ID: 120003184352
• NII Article ID: 110008900047
• NII Book ID: AA1123312X
• ISSN: 03029743
• ISSN: 15261719
• ISSN: 09135685
• ISSN: 16113349
• DOI: 10.1007/978-3-642-20877-5_44
• DOI: 10.7155/jgaa.00246
• NDL BIB ID: 11271122
• Web Site: http://hdl.handle.net/10119/9861
• Web Site: http://hdl.handle.net/10119/10303
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I11271122
• Web Site: http://link.springer.com/content/pdf/10.1007/978-3-642-20877-5_44
• Text Lang: en
• Article Type: journal article
• Data Source:
  • IRDB
  • NDL
  • Crossref
  • CiNii Articles
  • KAKEN