wiki_research

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

dominating_set (691B)

      1 # Dominating set
      2 
      3 https://en.wikipedia.org/wiki/Dominating_set
      4 
      5 A subset of vertices of a graph such that every vertex of the graph is either in the set or adjacent to a vertex in the set
      6 - distinguish [total_dominating_set] (aka "strongly-dominating set"): every vertex in the graph is adjacent to a vertex in the set, including the vertices in the set themselves. Does not always exist (e.g., isolated vertices)
      7 
      8 [karthik2019parameterized]: no [fixed_parameter_tractable] [approximation] algorithm for the problem
      9 - uses [abboud2017distributed]
     10 
     11 Generalization: [generalized_dominating_set]
     12 
     13 Variant: [independent_dominating_set]
     14 
     15 See also: [edge_dominating_set]
     16 
     17 Up: [graph_substructure]