wiki_research

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

treewidth (810B)

      1 # Treewidth
      2 
      3 A [width_measure] on [graphs]
      4 
      5 [treewidth_definition]
      6 
      7 ## Small values
      8 
      9 - [Graphs] of treewidth 1 are precisely [forests], including [trees]
     10 - [treewidth_2]
     11 
     12 ## Variants
     13 
     14 - [hypertreewidth]
     15 - [submodular_width]
     16 
     17 ## Related notions
     18 
     19 - [grid_minor]
     20 - [bramble]
     21 - [contraction] never makes treewidth increase
     22 
     23 ## Generalizations and related problems
     24 
     25 - [tree_decomposition_updating]
     26 - [semantic_treewidth] for [queries]
     27 - [graph_modification_treewidth]
     28 - [treewidth_directed]
     29 
     30 ## [Computational_problem]
     31 
     32 - [Treewidth_computation]
     33 - [Treewidth_approximation]
     34 
     35 ## Applications in [TCS]
     36 
     37 - [bidimensionality]
     38 
     39 ## Practical applications
     40 
     41 [treewidth_practical]
     42 
     43 Up: [width_measure]
     44 
     45 See also: [courcelle_theorem], [treelike_data], [message_passing], [pursuit_evasion], [elimination_order], [obstruction]