wiki_research

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

alpha_acyclic (710B)

      1 # Alpha acyclic
      2 
      3 Condition on [hypergraph]
      4 
      5 On [graph_undirected], equivalent to [graph_acyclic]
      6 
      7 Equivalent to [running_intersection_property]
      8 
      9 Equivalent to having a [join_tree]
     10 
     11 Equivalent to being both [hypergraph_conformal] and [hypergraph_chordal]
     12 
     13 Equivalent to [querywidth] and [hypertreewidth] and [generalized_hypertreewidth] being 1
     14 
     15 Defining paper proving the equivalences: [beeri1983desirability]
     16 
     17 Can be checked on [hypergraph_reduced], i.e., hyperedges that are covered by another hyperedge do not matter
     18 
     19 Can be tested in [linear_time] using [tarjan1984simple] via [chordal] and [hypergraph_chordal], but non-obvious
     20 
     21 Up: [degree_of_acyclicity]
     22 
     23 See also: [acyclic_hypergraph_sandwich_problem]