toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
  Record Links
Author (up) Li, B.; Moataz, F.Z.; Nisse, N.; Suchan, K. pdf  doi
  Title Minimum size tree-decompositions Type Journal Article
  Year 2018 Publication Discrete Applied Mathematics Abbreviated Journal Discret Appl. Math.  
  Volume 245 Issue Pages 109-127  
  Keywords Tree-decomposition; Treewidth; NP-hard  
  Abstract We study in this paper the problem of computing a tree-decomposition of a graph with width at most k and minimum number of bags. More precisely, we focus on the following problem: given a fixed k>=1, what is the complexity of computing a tree-decomposition of width at most k with minimum number of bags in the class of graphs with treewidth at most k? We prove that the problem is NP-complete for any fixed k>=4 and polynomial for k<=2; for k=3, we show that it is polynomial in the class of trees and 2-connected outerplanar graphs.  
  Corporate Author Thesis  
  Publisher Place of Publication Editor  
  Language Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0166-218x ISBN Medium  
  Area Expedition Conference  
  Notes Approved no  
  Call Number UAI @ eduardo.moreno @ Serial 864  
Permanent link to this record
Select All    Deselect All
 |   | 

Save Citations:
Export Records: