Testing orientability for matroids is NP-complete

DOI10.1006/AAMA.1999.0648MaRDI QIDQ1809523zbMATH OpenOpenAlexFDO

Authors 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

NP-completeoriented matroidspseudolines

Mathematics Subject Classification ID

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

Recommendations

• Invariant theory-like theorems for matroids and oriented matroids
• scientific article; zbMATH DE number 4106867
• A guided tour through oriented matroid axioms
• scientific article; zbMATH DE number 53152

Cites work

• scientific article; zbMATH DE number 4092241 (Why is no real title available?)
• scientific article; zbMATH DE number 17663 (Why is no real title available?)
• scientific article; zbMATH DE number 53152 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Oriented matroids
• Some minimal non-orientable matroids of rank three
• Teilungen der Ebenen durch Geraden oder topologische Geraden

Cited in

(10)

• On minimal non-orientable matroids with 2n elements and rank n
• Invariant theory-like theorems for matroids and oriented matroids
• Diameters of cocircuit graphs of oriented matroids: an update
• On the Query Complexity of Testing Orientations for Being Eulerian
• Weak orientability of matroids and polynomial equations
• Generation of oriented matroids using satisfiability solvers
• Representing matroids over the reals is \(\exists \mathbb{R}\)-complete
• Matroid enumeration for incidence geometry
• Combinatorial polar orderings and recursively orderable arrangements
• Minimal non-orientable matroids in a projective plane

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1809523)