✦ LIBER ✦
Testing Orientability for Matroids is NP-Complete
✍ Scribed by Jürgen Richter-Gebert
- Publisher
- Elsevier Science
- Year
- 1999
- Tongue
- English
- Weight
- 146 KB
- Volume
- 23
- Category
- Article
- ISSN
- 0196-8858
No coin nor oath required. For personal study only.
✦ Synopsis
Matroids and oriented matroids are fundamental objects in combinatorial geometry. While matroids model the behavior of vector configurations over general fields, oriented matroids model the behavior of vector configurations over ordered fields. For every oriented matroid there is a corresponding underlying matroid. This article addresses the question how complex it is to algorithmically decide whether, on the other hand, one can assign an orientation to a given (rank 3) matroid. We will prove that this problem is NP-complete.