Matroid complexity and non-succinct descriptions

Details Matroid complexity and non-succinct descriptions Matroid complexity and non-succinct descriptions

2007-02-20

arxiv.org/abs/math/0702567v2

Mathematics

Combinatorics

16 pages, 1 figure. Title changed, proofs simplified, a small amount of new material

Scientific paper

We investigate an approach to matroid complexity that involves describing a matroid via a list of independent sets, bases, circuits, or some other family of subsets of the ground set. The computational complexity of algorithmic problems under this scheme appears to be highly dependent on the choice of input-type. We define an order on the various methods of description, and we show how this order acts upon ten types of input. We also show that under this approach several natural algorithmic problems for matroids are complete in classes thought not to be equal to P.

Affiliated with

Also associated with

No associations

Rating

Matroid complexity and non-succinct descriptions 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 Matroid complexity and non-succinct descriptions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Matroid complexity and non-succinct descriptions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-383620