Computing an evolutionary ordering is hard

DOI10.1016/j.endm.2015.07.043zbMath1347.05154arXiv1410.6663OpenAlexW1517270671MaRDI QIDQ324805

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)

Cites Work

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

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