Name
Abstract | ||
|---|---|---|
This paper is devoted to the study of contiguity orders i.e. orders having a linear extension L such that all upper (or lower) cover sets are intervals of L. This new class appears to be a strict generalization of both interval orders and N-free orders, and is linearly recognizable. It is proved that computing the number of contiguity extensions is #P-complete, and that the dimension of height one contiguity orders is polynomially tractable. Moreover the membership is a comparability invariant on bi-contiguity orders. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1007/3-540-61576-8_89 | Combinatorics and Computer Science |
Keywords | DocType | ISBN |
Contiguity Orders | Conference | 3-540-61576-8 |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vincent Bouchitté | 1 | 172 | 12.07 |
| Abdelmajid Hilali | 2 | 0 | 0.34 |
| Roland Jégou | 3 | 18 | 2.64 |
| Jean-Xavier Rampon | 4 | 86 | 15.03 |