wiki_research

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

path_partition (309B)

      1 # Path partition
      2 
      3 Given an [undirected_graph] G, compute a minimum-cardinality *path partition*, i.e., a set of pairwise disjoint paths covering the [vertices] of G
      4 
      5 Mentioned in [foucaud2025polynomial]
      6 
      7 [NP_hard] because it generalizes the [Hamiltonian_path_problem]
      8 
      9 See also: [path_cover], [graph_packing]