Representation of an order as union of interval orders

@inproceedings{citeulike:2618292, abstract = {We present an practical method to obtain a compact computer memory representation of orders and to compute pairwise comparisons efficiently. The principle of this method is to represent an order P as a union of interval orders P i for which an optimal representation is already known (i.e. a union representation of P [Wes85]). For a directed acyclic graph G = (X, U) representing an order P = (X, <p), the preprocessing time complexity is not better than the transitive closure computation cost. In the worst case, the size of the representation is the same that the size of the transitive closure. However, experimental tests give better results, and comparison with the compression technique of Agrawal \& al. [ABJ89] is at the advantage of our method for dense orders.}, author = {Capelle, Christian }, booktitle = {Orders, Algorithms, and Applications: International Workshop ORDAL '94 Lyon, France, July 4–8, 1994 Proceedings}, citeulike-article-id = {2618292}, doi = {10.1007/BFb0019432}, keywords = {algorithms, data\_structure, order}, posted-at = {2008-04-01 02:36:45}, priority = {2}, series = {Lecture Notes in Computer Science}, title = {Representation of an order as union of interval orders}, url = {http://dx.doi.org/10.1007/BFb0019432}, volume = {831}, year = {1994} }

TY - CONF ID - citeulike:2618292 L3 - citeulike-article-id:2618292 TI - Representation of an order as union of interval orders T2 - Orders, Algorithms, and Applications: International Workshop ORDAL '94 Lyon, France, July 4–8, 1994 Proceedings SE - Lecture Notes in Computer Science VL - 831 N2 - We present an practical method to obtain a compact computer memory representation of orders and to compute pairwise comparisons efficiently. The principle of this method is to represent an order P as a union of interval orders P i for which an optimal representation is already known (i.e. a union representation of P [Wes85]). For a directed acyclic graph G = (X, U) representing an order P = (X, <p), the preprocessing time complexity is not better than the transitive closure computation cost. In the worst case, the size of the representation is the same that the size of the transitive closure. However, experimental tests give better results, and comparison with the compression technique of Agrawal & al. [ABJ89] is at the advantage of our method for dense orders. KW - algorithms KW - data_structure KW - order AU - Capelle, Christian PY - 1994/// UR - http://dx.doi.org/10.1007/BFb0019432 ER -