کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418637 | 681701 | 2010 | 8 صفحه PDF | دانلود رایگان |
We resolve the computational complexity of determining the treelength of a graph, thereby solving an open problem of Dourisboure and Gavoille, who introduced this parameter, and asked to determine the complexity of recognizing graphs of a bounded treelength Dourisboure and Gavoille (2007) [6]. While recognizing graphs with treelength 1 is easily seen as equivalent to recognizing chordal graphs, which can be done in linear time, the computational complexity of recognizing graphs with treelength 2 was unknown until this result. We show that the problem of determining whether a given graph has a treelength at most kk is NP-complete for every fixed k≥2k≥2, and use this result to show that treelength in weighted graphs is hard to approximate within a factor smaller than 32. Additionally, we show that treelength can be computed in time O∗(1.7549n)O∗(1.7549n) by giving an exact exponential time algorithm for the Chordal Sandwich problem and showing how this algorithm can be used to compute the treelength of a graph.
Journal: Discrete Applied Mathematics - Volume 158, Issue 7, 6 April 2010, Pages 820–827