Permanents, Pfaffian orientations, and even directed circuits
From MaRDI portal
Publication:1971908
DOI10.2307/121059zbMath0947.05066arXivmath/9911268OpenAlexW2064153357MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Determinants, permanents, traces, other special matrix functions (15A15) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Related Items (93)
Complexity of fixed point counting problems in Boolean networks ⋮ Max-algebra: The linear algebra of combinatorics? ⋮ Dimers on the \(3^3 . 4^2\) lattice ⋮ Regular bipartite graphs with all 2-factors isomorphic ⋮ On the skew-permanental polynomials of orientation graphs ⋮ Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians ⋮ PERFECT MATCHINGS AND GENUS OF SOME CARTESIAN PRODUCTS OF GRAPHS ⋮ On the even permutation polytope ⋮ Even circuits in oriented matroids ⋮ Computing Maximal Autarkies with Few and Simple Oracle Queries ⋮ A quadratic identity for the number of perfect matchings of plane graphs ⋮ Backdoors to Satisfaction ⋮ Replacing Pfaffians and applications ⋮ Generating bricks ⋮ Convertible subspaces of Hessenberg-type matrices ⋮ Diagram monoids and Graham-Houghton graphs: idempotents and generating sets of ideals ⋮ Finding a path with two labels forbidden in group-labeled graphs ⋮ Matching structure of symmetric bipartite graphs and a generalization of Pólya's problem ⋮ Computing the inertia from sign patterns ⋮ A conjecture of Norine and Thomas for abelian Cayley graphs ⋮ On the Pólya permanent problem over finite fields ⋮ Pfaffian graphs embedding on the torus ⋮ Thin edges in braces ⋮ A generalization of Little's theorem on Pfaffian orientations ⋮ A sufficient condition for Pfaffian graphs on the torus ⋮ On the dimer problem of the vertex-edge graph of a cubic graph ⋮ The Pfaffian property of graphs on the Möbius strip based on topological resolution ⋮ Minimal braces ⋮ Lattice point of view for argumentation framework ⋮ Binary linear codes, dimers and hypermatrices ⋮ Even cycles and perfect matchings in claw-free plane graphs ⋮ A Polynomial Time Algorithm for Recognizing Near-Bipartite Pfaffian Graphs ⋮ On the complexity of feedback set problems in signed digraphs ⋮ Matching connectivity: on the structure of graphs with perfect matchings ⋮ A matching-minor monotone parameter for bipartite graphs ⋮ Synchronizing Boolean networks asynchronously ⋮ Finding kernels or solving SAT ⋮ On spanning galaxies in digraphs ⋮ On the Number of α-Orientations ⋮ Matching signatures and Pfaffian graphs ⋮ Excluding a planar matching minor in bipartite graphs ⋮ Equilibria of graphical games with symmetries ⋮ The characteristic polynomial and the matchings polynomial of a weighted oriented graph ⋮ 2-factor Hamiltonian graphs. ⋮ The Pfaffian property of Cayley graphs on dihedral groups ⋮ On the rank of a real skew symmetric matrix described by an oriented graph ⋮ Out-degree reducing partitions of digraphs ⋮ Pfaffian orientations for a type of bipartite graph ⋮ Enumeration of perfect matchings of the Cartesian products of graphs ⋮ On the hardness of efficiently approximating maximal non-\(L\) submatrices. ⋮ Pfaffian polyominos on the Klein bottle ⋮ Positive and negative cycles in Boolean networks ⋮ Solving linear programs from sign patterns ⋮ Sign-solvable linear complementarity problems ⋮ The Pfaffian property of circulant graphs ⋮ Packing directed circuits exactly ⋮ Binary linear codes via 4D discrete Ihara-Selberg function ⋮ Polynomial recognition of equal unions in hypergraphs with few vertices of large degree ⋮ Face-width of Pfaffian braces and polyhex graphs on surfaces ⋮ An \(O(|E(G)|^2)\) algorithm for recognizing Pfaffian graphs of a type of bipartite graphs ⋮ Minimally non-Pfaffian graphs ⋮ Odd properly colored cycles in edge-colored graphs ⋮ Arithmetic matrix operations that preserve conversion ⋮ Augmenting tractable fragments of abstract argumentation ⋮ A note on the parity assignment problem ⋮ The Pfaffian property of Cartesian products of graphs ⋮ Brace generation ⋮ On the number of dissimilar pfaffian orientations of graphs ⋮ Recognizing near-bipartite Pfaffian graphs in polynomial time ⋮ Pfaffian orientations and perfect matchings of scale-free networks ⋮ On essentially 4-edge-connected cubic bricks ⋮ 2-extendability of toroidal polyhexes and Klein-bottle polyhexes ⋮ Minimum \(k\)-critical bipartite graphs ⋮ Counting the number of perfect matchings, and generalized decision trees ⋮ Some Results on Injectivity and Multistationarity in Chemical Reaction Networks ⋮ The combinatorics of N. G. de Bruijn ⋮ On the permanental polynomials of matrices ⋮ Cache me if you can: capacitated selfish replication games in networks ⋮ Graph characterization of fully indecomposable nonconvertible (0, 1)-matrices with minimal number of ones ⋮ Pfaffian pairs and parities: counting on linear matroid intersection and parity problems ⋮ A new proof of a characterisation of Pfaffian bipartite graphs ⋮ Strong orientations without even directed circuits ⋮ Spanning galaxies in digraphs ⋮ Colouring non-even digraphs ⋮ A characterisation of Pfaffian near bipartite graphs ⋮ Oriented Euler complexes and signed perfect matchings ⋮ Some results on the structure and spectra of matrix-products ⋮ Backdoors to tractable answer set programming ⋮ Matching theory and Barnette's conjecture ⋮ Enumeration of perfect matchings of a type of Cartesian products of graphs ⋮ Pfaffian Pairs and Parities: Counting on Linear Matroid Intersection and Parity Problems ⋮ Threshold function of ray nonsingularity for uniformly random ray pattern matrices ⋮ Odd \(K_{3,3}\) subdivisions in bipartite graphs
This page was built for publication: Permanents, Pfaffian orientations, and even directed circuits
