wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

treelength (484B)

      1 # Treelength
      2 
      3 Minimal [diameter] of a [tree_decomposition]
      4 
      5 https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_decompositions/tree_decomposition.html
      6 - "While deciding whether a graph has [treelength] 1 can be done in linear time (equivalent to deciding if the graph is [chordal]), deciding if it has treelength at most k for any fixed constant k is [NP_complete] by [lokshtanov2010complexity]."
      7 
      8 Up: [width_measure]
      9 
     10 See also: [tree_depth], [treewidth], [pathwidth]