Pfaffian orientations for a type of bipartite graph

DOI10.1016/J.TCS.2014.01.030MaRDI QIDQ2437778zbMATHOpenAlexFDO

Authors Fuliang Lu, Feng-Gen Lin, Lianzhu Zhang

Publication date 13 March 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.01.030

zbMATH Keywords

bipartite graphPfaffian orientation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Recommendations

• An \(O(|E(G)|^2)\) algorithm for recognizing Pfaffian graphs of a type of bipartite graphs
• A survey of Pfaffian orientations of graphs
• Enumeration of perfect matchings of the Cartesian products of graphs
• Pfaffian graphs embedding on the torus
• A characterisation of Pfaffian near bipartite graphs

Cites work

• scientific article; zbMATH DE number 13859 (Why is no real title available?)
• scientific article; zbMATH DE number 3517179 (Why is no real title available?)
• scientific article; zbMATH DE number 3326387 (Why is no real title available?)
• A characterisation of Pfaffian near bipartite graphs
• A characterization of convertible (0,1)-matrices
• Even circuits of prescribed clockwise parity
• Matching structure and the matching lattice
• Matching theory
• Minimally non-Pfaffian graphs
• Permanents, Pfaffian orientations, and even directed circuits
• Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
• Towards a characterisation of Pfaffian near bipartite graphs

Cited in

(12)

• An \(O(|E(G)|^2)\) algorithm for recognizing Pfaffian graphs of a type of bipartite graphs
• The Pfaffian property of Cartesian products of graphs
• Computing the permanental polynomials of bipartite graphs by Pfaffian orientation
• Bipartite graphs obtained from adjacency matrices of orientations of graphs
• A survey of Pfaffian orientations of graphs
• Oriented bipartite graphs and the Goldbach graph
• scientific article; zbMATH DE number 3910442 (Why is no real title available?)
• Even Orientations and Pfaffian graphs
• Pfaffian orientation and enumeration of perfect matchings for some Cartesian products of graphs
• Face-width of Pfaffian braces and polyhex graphs on surfaces
• On the number of dissimilar pfaffian orientations of graphs
• The Pfaffian property of circulant graphs

This page was built for publication: Pfaffian orientations for a type of bipartite graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437778)