Permanents, Pfaffian orientations, and even directed circuits
DOI10.2307/121059zbMath0947.05066arXivmath/9911268MaRDI QIDQ1971908
Neil Robertson, Robin Thomas, P. D. Seymour
Publication date: 23 March 2000
Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/9911268
characterization; polynomial-time algorithm; determinant; permanent; Pfaffian orientations; Pólya matrix
68Q25: Analysis of algorithms and problem complexity
05B20: Combinatorial aspects of matrices (incidence, Hadamard, etc.)
15A15: Determinants, permanents, traces, other special matrix functions
68R10: Graph theory (including graph drawing) in computer science
05C38: Paths and cycles
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C75: Structural characterization of families of graphs
05C85: Graph algorithms (graph-theoretic aspects)
05C20: Directed graphs (digraphs), tournaments
Related Items
