Testing orientability for matroids is NP-complete

DOI10.1006/aama.1999.0648zbMath0934.05039OpenAlexW2058299944MaRDI QIDQ1809523

Jürgen Richter-Gebert

Publication date: 10 April 2000

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/30231608695537580e5bd218d9d41be1941dd142

zbMATH Keywords

oriented matroidsNP-completepseudolines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items (6)

Diameters of cocircuit graphs of oriented matroids: an update ⋮ Combinatorial polar orderings and recursively orderable arrangements ⋮ Minimal non-orientable matroids in a projective plane ⋮ Matroid enumeration for incidence geometry ⋮ Weak orientability of matroids and polynomial equations ⋮ On minimal non-orientable matroids with \(2n\) elements and rank \(n\)

Cites Work

• Teilungen der Ebenen durch Geraden oder topologische Geraden
• Oriented matroids
• Some minimal non-orientable matroids of rank three
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Testing orientability for matroids is NP-complete