Back to University of Twente portal
An algorithmic characterization of antimatroids
Boyd, E. Andrew and Faigle, Ulrich (1990) An algorithmic characterization of antimatroids. Discrete Applied Mathematics, 28 (3). pp. 197-205. ISSN 0166-218X
![[img]](http://doc.utwente.nl/style/images/fileicons/application_pdf.png)
| PDF 551Kb |
| Abstract: | In an article entitled “Optimal sequencing of a single machine subject to precedence constraints” E.L. Lawler presented a now classical minmax result for job scheduling. In essence, Lawler's proof demonstrated that the properties of partially ordered sets were sufficient to solve the posed scheduling problem. These properties are, in fact, common to a more general class of combinatorial structures known as antimatroids, which have recently received considerable attention in the literature. It is demonstrated that the properties of antimatroids are not only sufficient but necessary to solve the scheduling problem posed by Lawler, thus yielding an algorithmic characterization of antimatroids. Examples of problems solvable by the general result are provided. |
| Item Type: | Article |
| Copyright: | © 1990 Elsevier |
| Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |
| Research Group: | |
| Link to this item: | http://purl.utwente.nl/publications/72792 |
| Official URL: | http://dx.doi.org/10.1016/0166-218X(90)90002-T |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page
Metis ID: 140508