Polynomial Time Recognition of Uniform Cocircuit Graphs

详细信息    查看全文

• 作者：Ricardo Gó ; mez Aiza ; Juan José ; Montellano Ballesteros ; Ricardo Strausz ; Kolja Knauer
• 关键词：Oriented matroid ; cocircuit graph ; recognition algorithm ; polynomial algorithm
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2009
• 出版时间：1 December 2009
• 年：2009
• 卷：35
• 期：Complete
• 页码：29-34
• 全文大小：188 K

文摘

We present an algorithm which takes a graph as input and decides in polynomial 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.