A poset dimension algorithm.
Loading...
Download
Official URL
Full text at PDC
Publication date
1999
Advisors (or tutors)
Editors
Journal Title
Journal ISSN
Volume Title
Publisher
Academic Press INC
Citations
Exportar
Citation
Yáñez, J., Montero, J.: A Poset Dimension Algorithm. Journal of Algorithms. 30, 185-208 (1999). https://doi.org/10.1006/jagm.1998.0974
Abstract
This article presents an algorithm which computes the dimension of an arbitrary finite poset (partial order set). This algorithm is based on the chromatic number of a graph instead of the classical approach based on the chromatic number of some hypergraph. The relation between both approaches is analyzed. With this algorithm, the dimension of many modest size posets can be computed. Otherwise, an upper bound for the poset dimension is obtained. Some computational results are included. (C) 1999 Academic Press.