𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Cocircuit Graphs and Efficient Orientation Reconstruction in Oriented Matroids

✍ Scribed by Eric Babson; Lukas Finschi; Komei Fukuda

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
294 KB
Volume
22
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the cocircuit graph G M of an oriented matroid M, which is the 1-skeleton of the cell complex formed by the span of the cocircuits of M. As a result of Cordovil, Fukuda, and Guedes de Oliveira, the isomorphism class of M is not determined by G M , but it is determined if M is uniform and the vertices in G M are paired if they are associated to negative cocircuits; furthermore the reorientation class of an oriented matroid M with rank(M) β‰₯ 2 is determined by G M if every vertex in G M is labeled by the zero support of the associated cocircuit. In this paper we show that the isomorphism class of a uniform oriented matroid is determined by the cocircuit graph, and we present polynomial algorithms which provide constructive proofs to all these results. Furthermore it is shown that the correctness of the input of the algorithms can be verified in polynomial time.

πŸ“œ SIMILAR VOLUMES

Longest paths and cycles in bipartite or
Longest paths and cycles in bipartite oriented graphs
✍ Zhang Ke Min πŸ“‚ Article πŸ“… 1987 πŸ› John Wiley and Sons 🌐 English βš– 430 KB πŸ‘ 1 views

In this paper we obtain two sufficient conditions, Ore type (Theorem 1) and Dirac type (Theorem 2). on the degrees of a bipartite oriented graph for ensuring the existence of long paths and cycles. These conditions are shown to be the best possible in a sense. An oriented graph is a digraph without

Some remarks on Arc-connectivity, vertex
Some remarks on Arc-connectivity, vertex splitting, and orientation in graphs and digraphs
✍ Bill Jackson πŸ“‚ Article πŸ“… 1988 πŸ› John Wiley and Sons 🌐 English βš– 309 KB

We apply proof techniques developed by L. Lovasz and A. Frank to obtain several results on the arc-connectivity of graphs and digraphs. The first results concern the operation of splitting two arcs from a vertex of an Eulerian graph or digraph in such a way as to preserve local connectivity conditio

On quadrilaterals in layers of the cube
On quadrilaterals in layers of the cube and extremal problems for directed and oriented graphs
✍ Schelp, Richard H.; Thomason, Andrew πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 286 KB πŸ‘ 2 views

ErdΕ‘s has conjectured that every subgraph of the n-cube Q n having more than (1/2+o(1))e(Q n ) edges will contain a 4-cycle. In this note we consider 'layer' graphs, namely, subgraphs of the cube spanned by the subsets of sizes k -1, k and k + 1, where we are thinking of the vertices of Q n as being

Demand-led and poverty-oriented … Or jus
Demand-led and poverty-oriented … Or just subcontracted and efficient? Learning from (semi-) privatized technology transfer programmes in Chile
✍ Anthony Bebbington; Octavio Sotomayor πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 201 KB

In the search for alternatives to state-managed agricultural research and extension, there has been much interest in assessing the pros and cons of, and the mechanisms for, varying forms of private sector involvement. One experience of privatization that has received much attention has been that of

Employee motivation, external orientatio
Employee motivation, external orientation and the technical efficiency of foreign-financed firms in China: a stochastic frontier analysis
✍ Vincent Mok; Godfrey Yeung πŸ“‚ Article πŸ“… 2005 πŸ› John Wiley and Sons 🌐 English βš– 174 KB πŸ‘ 1 views

## Abstract By using a stochastic frontier model, we have identified several firm‐specific attributes as determinants of technical efficiency in foreign‐financed manufacturing firms in southern China. The empirical results suggest a strong association between efficiency and employee motivation, whi