TAILIEUCHUNG - 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. . Box 305 Holon 58102 ISRAEL yuliak levitv @ 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 . 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

• Báo cáo khoa học
• Correspondence between
• algorithmic characterizations
• reports of mathematics
• mathematical works
• Even circuits
• prescribed clockwise parity
• scientific reports
• scientific research
• STRING TREE CORRESPONDENCE GRAMMAR A DECLARATIVE GRAMMAR FORMALISM
• DEFINING THE CORRESPONDENCE BETWEEN STRINGS OF TERMS
• TREE STRUCTURES
• model language
• process natural language
• báo cáo khoa học
• báo cáo hóa học
• công trình nghiên cứu về hóa học
• tài liệu về hóa học
• cách trình bày báo cáo
• Multi dimensional poverty
• Livelihood assets
• Principal component analysis
• Multiple correspondence analysis
• Cluster analysis
• MDS matrice
• MDS codes
• RS codes
• Maximum Distance Separable
• MDS matrix
• Genome Biology
• Single cell RNA seq
• Single cell epigenomics
• Manifold learning
• Manifold alignment
• Fruit maturity
• Molecular markers
• NAC transcription factor
• Ripening time
• Stone fruits
• Research methods
• Data collection methods
• Understanding scientific research
• Ensuring research validity
• Measurement techniques
• Sampling methods
• Scientific research capacity
• Educational institutions
• Policy and management studies
• Vietnam Academy for Ethnic minorities
• Scientific bases
• earth sciences
• Research
• VNU Journal of Science
• Action research
• linguistics
• research projects
• Foreign Languages
• cooperative research
• Renewable energy
• Introduction to research
• Scientific investigation
• Scientific investigation research
• Experimental designs
• Measurement of variables
• Reading research
• Conducting and reading research
• Research process
• Research report
• Purpose of research
• Scientific method
• Conducting research
• The effect of university autonomy on training and scientific research
• Vietnam national university of agriculture
• Training and scientific research
• Vascular plant
• Flora
• Yen Tu
• Quang Ninh Research Forest
• statements and documents scientific reports
• medical reports
• medical knowledge
• medical research
• clinical trials
• medical management
• health care
• Methods in behavioral research
• Behavioral research
• Scientific understanding
• Fundamental research issues
• Measurement concepts
• Observational methods
• reading comprehension
• education
• optimal picket
• model creation
• urban expansion
• organizing spatial
• Journal of Science
• Journal of Technology
• Technology Management
• Research quality
• Strategy and policy
• Summary of Doctoral thesis
• Summary of Doctoral thesis in public Management
• State management
• Female scientific research human
• Research human resource development
• Scientific research and teaching
• Defense and security education
• Current situation and solutions
• Security education
• Structural biochemistry
• epigenetics
• MicroRNAs
• Tạp chí khoa học
• Tạp chí Công nghệ
• Quản lý công nghệ
• Human resources
• Science management
• Poliomyelitis vaccine Research
• Non Ri Maprec
• Production center