2014/10/24 by Laurent Bulteau, Bulteau, Laurent, Gustavo Sacomoto +3
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC
paper · pdf · doi:10.48550/arxiv.1410.6663
arxiv created 2014/10/24 · arxiv updated 2014/10/27
We prove that computing an evolutionary ordering of a family of sets, i.e. an ordering where each set intersects with --but is not included in-- the union earlier sets, is NP-hard.