A Polynomial Time Algorithm for Recognizing Near-Bipartite Pfaffian Graphs

DOI10.1016/J.ENDM.2008.01.030MaRDI QIDQ3503547zbMATH OpenOpenAlexFDO

Authors Alberto Alexandre Assis Miranda, Cláudio L. Lucchesi

Publication date 5 June 2008

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2008.01.030

zbMATH Keywords

matching covered graphsmatching theoryPfaffian graphspolynomial time algorithms

Mathematics Subject Classification ID

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

Recommendations

• Recognizing near-bipartite Pfaffian graphs in polynomial time
• Towards a characterisation of Pfaffian near bipartite graphs
• scientific article; zbMATH DE number 3910442
• An \(O(|E(G)|^2)\) algorithm for recognizing Pfaffian graphs of a type of bipartite graphs
• A characterisation of Pfaffian near bipartite graphs

Cites work

• A characterisation of Pfaffian near bipartite graphs
• Matching theory
• On the number of dissimilar pfaffian orientations of graphs
• Permanents, Pfaffian orientations, and even directed circuits
• Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
• Pólya's permanent problem

Cited in

(6)

• Towards a characterisation of Pfaffian near bipartite graphs
• A generalization of Little's theorem on Pfaffian orientations
• On essentially 4-edge-connected cubic bricks
• A conjecture of Norine and Thomas for abelian Cayley graphs
• Algorithms for recognizing bipartite-Helly and bipartite-conformal hypergraphs
• Recognizing near-bipartite Pfaffian graphs in polynomial time

This page was built for publication: A Polynomial Time Algorithm for Recognizing Near-Bipartite Pfaffian Graphs

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