Recognizing near-bipartite Pfaffian graphs in polynomial time

DOI10.1016/J.DAM.2009.01.008MaRDI QIDQ987672zbMATH OpenOpenAlexFDO

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

Publication date 13 August 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2009.01.008

zbMATH Keywords

matching covered graphsperfect matchingPfaffian graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• A Polynomial Time Algorithm for Recognizing Near-Bipartite Pfaffian Graphs
• Minimally non-Pfaffian graphs
• An \(O(|E(G)|^2)\) algorithm for recognizing Pfaffian graphs of a type of bipartite graphs
• A characterisation of Pfaffian near bipartite graphs
• Matching signatures and Pfaffian 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

(9)

• Towards a characterisation of Pfaffian near bipartite graphs
• An \(O(|E(G)|^2)\) algorithm for recognizing Pfaffian graphs of a type of bipartite graphs
• A characterisation of Pfaffian near bipartite graphs
• Recognizing generalized Petersen graphs in linear time
• Bipartite double cover and perfect 2-matching covered graph with its algorithm
• A Polynomial Time Algorithm for Recognizing Near-Bipartite Pfaffian Graphs
• Efficiently recognizing the P₄-structure of trees and of bipartite graphs without short cycles
• A note on cyclic connectivity and matching properties of regular graphs
• Minimally non-Pfaffian graphs

This page was built for publication: Recognizing near-bipartite Pfaffian graphs in polynomial time

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