“Matroid embedding”的意思、由来-开放百科全书

词条

Matroid embedding

释义

References

In combinatorics, a matroid embedding is a set system (F, E), where F is a collection of feasible sets, that satisfies the following properties:

(Accessibility Property) Every non-empty feasible set X contains an element x such that X\\{x} is feasible;
(Extensibility Property) For every feasible subset X of a basis (i.e., maximal feasible set) B, some element in B but not in X belongs to the extension ext(X) of X, where ext(X) is the set of all elements e not in X such that X∪{e} is feasible;
(Closure-Congruence Property) For every superset A of a feasible set X disjoint from ext(X), A∪{e} is contained in some feasible set for either all or no e in ext(X);
The collection of all subsets of feasible sets forms a matroid.

Matroid embedding was introduced by {{harvtxt|Helman|Moret|Shapiro|1993}} to characterize problems that can be optimized by a greedy algorithm.

References

{{citation

| last1 = Helman | first1 = Paul
| last2 = Moret | first2 = Bernard M. E. | author2-link = Bernard Moret
| last3 = Shapiro | first3 = Henry D.
| doi = 10.1137/0406021
| issue = 2
| journal = SIAM Journal on Discrete Mathematics
| mr = 1215233
| pages = 274–283
| title = An exact characterization of greedy structures
| volume = 6
| year = 1993| citeseerx = 10.1.1.37.1825}}

1 : Matroid theory

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。