首页 | 本学科首页   官方微博 | 高级检索  
     检索      


On the complexity of computing treelength
Authors:Daniel Lokshtanov
Institution:Department of Informatics, University of Bergen, N-5020 Bergen, Norway
Abstract: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 k is NP-complete for every fixed k≥2, and use this result to show that treelength in weighted graphs is hard to approximate within a factor smaller than View the MathML source. Additionally, we show that treelength can be computed in time 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.
Keywords:Graph treelength  NP-complete  Approximation  Inapproximability  Exact exponential algorithm  Chordal sandwich problem
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号