Cubic Time Recognition of Cocircuit Graphs of Uniform Oriented Matroids

Details Cubic Time Recognition of Cocircuit Graphs of Uniform Oriented Matroids Cubic Time Recognition of Cocircuit Graphs of Uniform Oriented Matroids

2010-01-20

arxiv.org/abs/1001.3534v1

Mathematics

Combinatorics

9 pages

Scientific paper

We present an algorithm which takes a graph as input and decides in cubic time if the graph is the cocircuit graph of a uniform oriented matroid. In the affirmative case the algorithm returns the set of signed cocircuits of the oriented matroid. This improves an algorithm proposed by Babson, Finschi and Fukuda. Moreover we strengthen a result of Montellano-Ballesteros and Strausz about crabbed connectivity of cocircuit graphs of uniform oriented matroids.

Affiliated with

Also associated with

No associations

Rating

Cubic Time Recognition of Cocircuit Graphs of Uniform Oriented Matroids does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Cubic Time Recognition of Cocircuit Graphs of Uniform Oriented Matroids, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cubic Time Recognition of Cocircuit Graphs of Uniform Oriented Matroids will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-128663