Computing an evolutionary ordering is hard

DOI10.1016/J.ENDM.2015.07.043MaRDI QIDQ324805zbMATH OpenOpenAlexFDO

Authors Laurent Bulteau, Gustavo Sacomoto, Blerina Sinaimeri

Publication date 17 October 2016

Full work available at URL https://arxiv.org/abs/1410.6663

zbMATH Keywords

complexityear-decompositionevolutionary family

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: 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.

Recommendations

• Evolutionary families of sets
• scientific article; zbMATH DE number 1302179
• On the computational complexity of ordered subgraph recognition
• Tree reconstruction from partial orders
• NP-completeness results concerning greedy and super greedy linear extensions

Cites work

• A simplified NP-complete satisfiability problem
• Ear Decompositions of Elementary Graphs and GF2-rank of Perfect Matchings
• Ear decompositions of matching covered graphs
• Evolutionary families of sets
• Matching theory

Cited in

(1)

• scientific article; zbMATH DE number 3869125 (Why is no real title available?)

This page was built for publication: Computing an evolutionary ordering is hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q324805)