[ont.events] Combinatorics Seminar - Searching and Scheduling in Ordered Sets by G. Steiner, McMaster Univ.

voula@utcsri.UUCP (Voula Vanneli) (03/19/85)

                   UNIVERSITY OF TORONTO
               DEPARTMENT OF COMPUTER SCIENCE
          (_G_B = _G_a_l_b_r_a_i_t_h _B_u_i_l_d_i_n_g, _3_5 _S_t. _G_e_o_r_g_e)

                  Professor George Steiner
          School of Business, McMaster University

         "Searching and Scheduling in Ordered Sets"

                          Abstract

     We discuss the problem of retrieving data from  ordered
data structures and its relationship to many well-known pre-
cedence constrained scheduling problems. The  complexity  of
all  these  problems  depends  on  how  efficiently  we  can
enumerate the ideals of the  underlying  ordered  structure.
As  a  special  case of this generally difficult problem, we
present a labelling scheme which  counts  the  ideals  of  a
two-dimensional  partial order in polynomial time.  Based on
this scheme, we show how  the  central  element  of  a  two-
dimensional partial order can be located in polynomial time.