Cubic time recognition of cocircuit graphs of uniform oriented matroids (Q607364): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Cocircuit graphs and efficient orientation reconstruction in oriented matroids / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4003411 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Oriented matroids and combinatorial manifolds / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the cocircuit graph of an oriented matroid / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Oriented matroids / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A characterization of cocircuit graphs of uniform oriented matroids / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Shelling polyhedral 3-balls and 4-polytopes / rank | |||
Normal rank |
Latest revision as of 12:41, 3 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Cubic time recognition of cocircuit graphs of uniform oriented matroids |
scientific article |
Statements
Cubic time recognition of cocircuit graphs of uniform oriented matroids (English)
0 references
22 November 2010
0 references
Uniform oriented matroids are characterized by \textit{R. Cordovil, K. Fukuda} and \textit{A. Guedes de Oliveira}, ``On the cocircuit graph of an oriented matroid,'' Discrete Comput. Geom. 24, No.\,2--3, 257--265 (2000; Zbl 0958.52016)] in terms of cocircuit graphs with an antipodal labeling and by \textit{J. J. Montellano-Ballesteros} and \textit{R. Strausz} [``A characterization of cocircuit graphs of uniform oriented matroids,'' J. Comb. Theory, Ser. B 96, No. 4, 445--454 (2006; Zbl 1109.52016)] via sign-labeled cocircuit graphs. In the paper under review the concept of crabbed connectivity is introduced and a strengthened version of the main theorem in the above cited work of Montellano-Ballesteros and Strausz is proved and used to provide an algorithm that decides whether a given graph is the cocircuit graph of a uniform oriented matroid. The running time is better than the one given in [\textit{E. Babson, L. Finschi} and \textit{K. Fukuda}, ``Cocircuit graphs and efficient orientation reconstruction in oriented matroids,'' Eur. J. Comb. 22, No.\,5, 587--600 (2001; Zbl 0988.52032)]. Some open problems to further improve the running time are formulated in terms of the diameter of the cocircuit graph and antipodal labellings.
0 references
uniform matroid
0 references
cocircuit graph
0 references
crabbed connectivity
0 references