论文标题
甚至是定向的矩形的电路
Even Circuits in Oriented Matroids
论文作者
论文摘要
在本文中，我们概括了均匀的定向循环问题，该问题询问给定的挖掘物是否包含偶数长度的定向循环，以定向常规矩阵的方向。我们定义了不合时宜的基型概括非二次挖掘的概括，这在解决偶数级别问题的计算复杂性方面发挥了核心作用。然后，我们表明，在常规矩阵中检测到均匀的电路的问题在多个评估上等同于识别非平方向的矩阵。我们的主要结果是根据禁止的未成年人对非平方键基矩阵的精确表征，这补充了Seymour和Thomassen对非平衡的图形矩阵的现有表征。
In this paper we generalise the even directed cycle problem, which asks whether a given digraph contains a directed cycle of even length, to orientations of regular matroids. We define non-even oriented matroids generalising non-even digraphs, which played a central role in resolving the computational complexity of the even dicycle problem. Then we show that the problem of detecting an even directed circuit in a regular matroid is polynomially equivalent to the recognition of non-even oriented matroids. Our main result is a precise characterisation of the class of non-even oriented bond matroids in terms of forbidden minors, which complements an existing characterisation of non-even oriented graphic matroids by Seymour and Thomassen.
