Matroid embedding

Matroid embedding

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

  1. (Accessibility Property) Every non-empty feasible set X contains an element x such that X\{x} is feasible;
  2. (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, or the set of all elements e not in X such that X∪{e} is feasible;
  3. (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);
  4. The collection of all subsets of feasible sets forms a matroid.

Matroid embedding was introduced by Helman et al. in 1993 to characterize problems that can be optimized by a greedy algorithm.

References

  • Helman, Paul; Moret, Bernard M. E.; Shapiro, Henry D. (1993). "An exact characterization of greedy structures". SIAM Journal of Discrete Mathematics 6 (2): 274–283. doi:10.1137/0406021. 

Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Greedoid — In combinatorics, a greedoid is a type of set system. It arises from the notion of the matroid, which was originally introduced by Whitney in 1935 to study planar graphs and was later used by Edmonds to characterize a class of optimization… …   Wikipedia

  • List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… …   Wikipedia

  • List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is …   Wikipedia

  • Dual graph — G′ is the dual graph of G In mathematics, the dual graph of a given planar graph G is a graph which has a vertex for each plane region of G, and an edge for each edge in G joining two neighboring regions, for a certain embedding of G. The term… …   Wikipedia

  • Duality (mathematics) — In mathematics, a duality, generally speaking, translates concepts, theorems or mathematical structures into other concepts, theorems or structures, in a one to one fashion, often (but not always) by means of an involution operation: if the dual… …   Wikipedia

  • Closure operator — In mathematics, a closure operator on a set S is a function cl: P(S) → P(S) from the power set of S to itself which satisfies the following conditions for all sets X,Y ⊆ S. X ⊆ cl(X) (cl is extensive) X ⊆ Y implies cl(X) ⊆ cl(Y)   (cl… …   Wikipedia

  • Edge coloring — A 3 edge coloring of the Desargues graph. In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge… …   Wikipedia

  • Wheel graph — infobox graph name = Wheel graph image caption = Several examples of wheel graphs vertices = n edges = 2( n − 1) chromatic number = 3 if n is odd 4 if n is even chromatic index = In the mathematical discipline of graph theory, a wheel graph W n… …   Wikipedia

  • Arboricity — The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning trees needed to cover all the edges of the graph.ExampleThe figure shows the… …   Wikipedia

  • Gain graph — A gain graph is a graph whose edges are labelled invertibly, or orientably, by elements of a group G . This means that, if an edge e in one direction has label g (a group element), then in the other direction it has label g −1. The label function …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”