Name
Abstract | ||
|---|---|---|
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 10 types of input. We also show that under this approach several natural algorithmic problems are complete in classes thought not to be equal to P. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1137/050640576 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
Matroid Complexity,order act,various method,independent set,algorithmic problem,Nonsuccinct Descriptions,computational complexity,ground set,natural algorithmic problem,input type | Matroid,Family of sets,Discrete mathematics,Combinatorics,Algorithmics,Oriented matroid,Matroid partitioning,Graphic matroid,Weighted matroid,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
22 | 2 | 0895-4801 |
Citations | PageRank | References |
4 | 0.87 | 3 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dillon Mayhew | 1 | 102 | 18.63 |