Orders, Algorithms, and Applications: International Workshop ORDAL ’94 Lyon, France, July 4–8, 1994 Proceedings

Michel Habib, Lhouari Nourine (auth.), Vincent Bouchitté, Michel Morvan (eds.)3540582746, 9783540582748

This volume is the proceedings of the first International Workshop on Orders, Algorithms, and Applications, held at Lyon, France in July 1994.
Ordered sets and the more specifically algorithmic aspects of order theory are of increasing importance, for example in graph theory. They enjoy a recognized place in computer science as well as in mathematics, due to various new developments in the last few years. The nine technical papers accepted for this volume and the four invited papers presented offer a representative perspective on theoretical and applicational aspects of orders and related algorithms.

---

Table of contents :
Bit-vector encoding for partially ordered sets….Pages 1-12
Intervals and orders: What comes after interval orders?….Pages 13-32
Dimension and algorithms….Pages 33-52
Upward drawings to fit surfaces….Pages 53-58
A cleanup on transitive orientation….Pages 59-85
A characterization of graphs with vertex cover up to five….Pages 86-99
Testing hereditary properties efficiently on average….Pages 100-116
Orders, k -sets and fast halfplane search on paged memory….Pages 117-127
Triangle graphs and their coloring….Pages 128-142
Representation of an order as union of interval orders….Pages 143-161
Minimal representation of semiorders with intervals of same length….Pages 162-175
The computation of the jump number of convex graphs….Pages 176-185
Fast lattice browsing on sparse representation….Pages 186-204