wiki_research

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

densest_subgraph (435B)

      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   - Connection to [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]