Name
Abstract | ||
|---|---|---|
A family of sets is evolutionary if it is possible to order its elements such that each set except the first one has an element in the union of the previous sets and also an element not in that union. This definition is inspired by a conjecture of Naddef and Pulleyblank concerning ear decompositions of 1-extendable graphs. Here we consider the problem of determining whether a family of sets is evolutionary. We show that the problem is NP-complete even when every set in the family has at most 3 elements and each element appears at most a constant number of times. In contrast, for families of intervals of integers, we provide a polynomial time algorithm for the problem. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.endm.2015.07.043 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
evolutionary family,ear-decomposition,complexity | Integer,Discrete mathematics,Family of sets,Graph,Combinatorics,Ear decomposition,Time complexity,Conjecture,Mathematics | Journal |
Volume | ISSN | Citations |
50 | 1571-0653 | 0 |
PageRank | References | Authors |
0.34 | 3 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Laurent Bulteau | 1 | 0 | 0.34 |
| Gustavo Sacomoto | 2 | 45 | 5.81 |
| B. Sinaimeri | 3 | 47 | 11.75 |