Thesis icon

Thesis

Matroids and complexity

Abstract:

We consider different ways of describing a matroid to a Turing machine by listing the members of various families of subsets, and we construct an order on these different methods of description. We show that, under this scheme, several natural matroid problems are complete in classes thought not to be equal to P.

We list various results linking parameters of basis graphs to parameters of their associated matroids. For small values of k we determine which matroids have the clique numb...

Expand abstract

Actions


Access Document


Files:

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Mathematical Institute
Research group:
Combinatorics
Oxford college:
Christ Church
Role:
Author

Contributors

Division:
MPLS
Department:
Mathematical Institute
Role:
Supervisor
Publication date:
2005
Type of award:
DPhil
Level of award:
Doctoral
Awarding institution:
University of Oxford
Language:
English
Keywords:
Subjects:
UUID:
uuid:23640923-17c3-4ad8-9845-320e3b662910
Local pid:
ora:6095
Deposit date:
2012-03-01

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP