An O(|E(G)|^2) algorithm for recognizing Pfaffian graphs of a type of bipartite graphs

DOI10.1007/S10878-017-0207-0MaRDI QIDQ1743482zbMATH OpenOpenAlexFDO

Authors Xing Feng, Mingzu Zhang, Lianzhu Zhang

Publication date 13 April 2018

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-017-0207-0

zbMATH Keywords

bipartite graphperfect matchingPfaffian orientation

Mathematics Subject Classification ID

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

Recommendations

• Pfaffian orientations for a type of bipartite graph
• Pfaffian graphs embedding on the torus
• A survey of Pfaffian orientations of graphs
• scientific article; zbMATH DE number 3910442
• Recognizing near-bipartite Pfaffian graphs in polynomial time

Cites work

• A characterization of convertible (0,1)-matrices
• Double vertex-edge domination
• Global total Roman domination in graphs
• scientific article; zbMATH DE number 3326387 (Why is no real title available?)
• Matching structure and the matching lattice
• Matching theory
• On the number of dissimilar pfaffian orientations of graphs
• Permanents, Pfaffian orientations, and even directed circuits
• Pfaffian graphs embedding on the torus
• Pfaffian orientations for a type of bipartite graph
• Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
• Pólya's permanent problem
• The complexity of computing the permanent
• The Pfaffian property of Cartesian products of graphs
• The Pfaffian property of circulant graphs
• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice

Cited in

(7)

• Towards a characterisation of Pfaffian near bipartite graphs
• Pfaffian orientations for a type of bipartite graph
• Algorithms for recognizing bipartite-Helly and bipartite-conformal hypergraphs
• A Polynomial Time Algorithm for Recognizing Near-Bipartite Pfaffian Graphs
• scientific article; zbMATH DE number 3910442 (Why is no real title available?)
• Pfaffian graphs embedding on the torus
• Recognizing near-bipartite Pfaffian graphs in polynomial time

This page was built for publication: An \(O(|E(G)|^2)\) algorithm for recognizing Pfaffian graphs of a type of bipartite graphs

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