wiki_research

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

densest_subgraph (426B)

      1 # Densest subgraph
      2 
      3 https://en.wikipedia.org/wiki/Dense_subgraph
      4 
      5 Find subgraph of maximal density (#edges/#vertices) of input graph
      6 
      7 - Goldberg's algorithm: This is in [ptime] and reducible to [network_flow]
      8   - Lien avec [submodularity]/[supermodularity], cf [chekuri2022densest]
      9 - Also a [greedy_algorithm] (Charikar's algorithm)
     10 - Efficient algorithms on some graph classes, e.g., [harpeled2024approximating]
     11 
     12 Up: [graph]