Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo khoa học: Correspondence between two antimatroid algorithmic characterizations

The basic distinction between already known algorithmic characterizations of matroids and antimatroids is in the fact that for antimatroids the ordering of elements is of great importance. While antimatroids can also be characterized as set systems, the question whether there is an algorithmic description of antimatroids in terms of sets and set functions was open for some period of time. | Correspondence between two antimatroid algorithmic characterizations Yulia Kempner and Vadim E. Levit Department of Computer Science Holon Academic Institute of Technology 52 Golomb Str. P.O. Box 305 Holon 58102 ISRAEL yuliak levitv @hait.ac.il Submitted Aug 14 2003 Accepted Nov 6 2003 Published Nov 17 2003 MR Subject Classifications 90C27 05B35 Abstract The basic distinction between already known algorithmic characterizations of matroids and antimatroids is in the fact that for antimatroids the ordering of elements is of great importance. While antimatroids can also be characterized as set systems the question whether there is an algorithmic description of antimatroids in terms of sets and set functions was open for some period of time. This article provides a selective look at classical material on algorithmic characterization of antimatroids i.e. the ordered version and a new unordered version. Moreover we empathize formally the correspondence between these two versions. keywords antimatroid greedoid chain algorithm greedy algorithm monotone linkage function. 1 Introduction In this paper we compare two algorithmic characterization of antimatroids. There are many equivalent axiomatizations of antimatroids that may be separated into two categories antimatroids defined as set systems and antimatroids defined as languages. Boyd and Faigle 1 introduced an algorithmic characterization of antimatroids based on the language definition. Another characterization of antimatroids that considers them as set systems is the main topic of this paper. This characterization is based on the idea of optimization using set functions defined as minimum values of linkages between a set and the elements from the set complement. THE ELECTRONIC JOURNAL OF COMBINATORICS 10 2003 R44 1 Section 2 gives some basic information about antimatroids as set systems and introduces truncated antimatroids. In Section 3 monotone linkage functions are considered. Optimization of the functions defined as