wiki_research

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

arboricity (872B)

      1 # Arboricity
      2 
      3 A [width_measure] on [undirected_graphs]: the minimum number of [spanning_forests] needed to cover all [edges] of the [graph]
      4 - equivalently, the [minimum] number of [forests] in which the [edges] can be partitioned
      5 
      6 A [planar_graph] has arboricity at most 3
      7 
      8 Connection between [arboricity] and [dynamic_data] in [lu2021towards]
      9 
     10 - [chiba1985arboricity]
     11 - [danisch2018listing]
     12   - https://papers-gamma.link/paper/32
     13   - https://github.com/maxdan94/kmotif
     14 - [ortmann2014triangle] algorithm for [triangle_listing]
     15 
     16 [bressan2022complexity]: optimality of the results of [chiba1985arboricity] for [graph_pattern_counting]
     17 
     18 [computational_complexity]: can be computed in [polynomial] time, cf
     19 https://en.wikipedia.org/wiki/Arboricity#Algorithms
     20 - and [linear_time] 2-[approximations]
     21 
     22 Up: [width_measure]
     23 
     24 See also: [degeneracy], [thickness], [pseudoarboricity]