wiki_research

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

path_cover (350B)

      1 # Path cover
      2 
      3 Given an [undirected_graph] G, compute a minimum-cardinality *path cover*, i.e., a set of paths covering the [vertices] of G (not necessarily pairwise disjoint)
      4 
      5 Studied in [foucaud2025polynomial]
      6 
      7 [NP_hard] because it generalizes the [Hamiltonian_path_problem]
      8 
      9 See also: [graph_packing], [path_partition]
     10 
     11 Up: [computational_problem]