Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
From MaRDI portal
Publication:911300
DOI10.1016/0166-218X(89)90053-XzbMath0696.68076OpenAlexW1966874927MaRDI QIDQ911300
Vijay V. Vazirani, Mihalis Yannakakis
Publication date: 1989
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(89)90053-x
Analysis of algorithms and problem complexity (68Q25) 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)
Related Items
Generating bricks, Convertible subspaces of Hessenberg-type matrices, Diagram monoids and Graham-Houghton graphs: idempotents and generating sets of ideals, The number of matrices with nonzero permanent over a finite field, Matching structure of symmetric bipartite graphs and a generalization of Pólya's problem, Computing the inertia from sign patterns, On the Pólya permanent problem over finite fields, On the Gibson barrier for the Pólya problem, A generalization of Little's theorem on Pfaffian orientations, Minimal braces, A Polynomial Time Algorithm for Recognizing Near-Bipartite Pfaffian Graphs, On the complexity of feedback set problems in signed digraphs, Minimum degree of minimal \((n-10)\)-factor-critical graphs, Pfaffian orientations for a type of bipartite graph, Solving linear programs from sign patterns, Sign-solvable linear complementarity problems, 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, Pfaffian labelings and signs of edge colorings, Matching theory -- a sampler: From Dénes König to the present, Arithmetic matrix operations that preserve conversion, The Cubic Vertices of Minimal Bricks, The Even Cycle Problem for Directed Graphs, Minimal bricks, On the number of dissimilar pfaffian orientations of graphs, Recognizing near-bipartite Pfaffian graphs in polynomial time, Spanning trees of 3-uniform hypergraphs, Unnamed Item, The combinatorics of N. G. de Bruijn, Strong orientations without even directed circuits, Colouring non-even digraphs, Oriented Euler complexes and signed perfect matchings, Matching theory and Barnette's conjecture, Extending matchings in graphs: A survey
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- On the relation between the determinant and the permanent
- Signsolvability revisited
- Sign-nonsingular matrices and even cycles in directed graphs
- Even cycles in directed graphs
- Characterization of even directed graphs
- Matching theory
- NP is as easy as detecting unique solutions
- Matching is as easy as matrix inversion
- Constructing a perfect matching is in random NC
- Matching structure and the matching lattice
- NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
- Every 7-regular digraph contains an even cycle
- On digraphs with the odd cycle property
