Name
Abstract | ||
|---|---|---|
Let be a partial order and an arboreal extension of it (i.e. the Hasse diagram of is a rooted tree with a unique minimal element). A of is a relation contained in the Hasse diagram of , but not in the order . The of is the number of jumps contained in it. We study the problem of finding the arboreal extension of having minimum arboreal jump number—a problem related to the well-known (linear) jump number problem. We describe several results for this problem, including NP-completeness, polynomial time solvable cases and bounds. We also discuss the concept of a arboreal extension, namely an arboreal extension whose removal of one jump makes it no longer arboreal. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s11083-012-9246-4 | Order |
Keywords | Field | DocType |
Arboreal jump number,Order extensions,Greedy chain decompositions,Jump number,Partially ordered sets | Discrete mathematics,Combinatorics,Arboreal locomotion,Hasse diagram,Number problem,Maximal element,Time complexity,Jump,Mathematics,Partially ordered set | Journal |
Volume | Issue | ISSN |
30 | 1 | 0167-8094 |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Adriana P. Figueiredo | 1 | 0 | 0.34 |
| Michel Habib | 2 | 681 | 50.64 |
| Sulamita Klein | 3 | 308 | 32.86 |
| Jayme Luiz Szwarcfiter | 4 | 618 | 95.79 |