Output-sensitive algorithm for generating the flats of a matroid

Details Output-sensitive algorithm for generating the flats of a matroid Output-sensitive algorithm for generating the flats of a matroid

2011-07-21

arxiv.org/abs/1107.4301v1

Mathematics

Combinatorics

Scientific paper

We present an output-sensitive algorithm for generating the whole set of flats of a finite matroid. Given a procedure, P, that decides in S_P time steps if a set is independent, the time complexity of the algorithm is O(N^2 M S_P), where N and M are the input and output size, respectively. In the case of vectorial matroids, a specific algorithm is reported whose time complexity is equal to O(N^2 M d^2), d being the rank of the matroid. In some cases this algorithm can provide an efficient method for computing zonotopes in $H$-representation, given their representation in terms of Minkowski sum of known segments.

Affiliated with

Also associated with

No associations

Rating

Output-sensitive algorithm for generating the flats of a matroid does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Output-sensitive algorithm for generating the flats of a matroid, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Output-sensitive algorithm for generating the flats of a matroid will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-688097