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

Xing Feng (), Lianzhu Zhang () and Mingzu Zhang ()
Additional contact information
Xing Feng: Xiamen University
Lianzhu Zhang: Xiamen University
Mingzu Zhang: Xiamen University

Journal of Combinatorial Optimization, 2018, vol. 35, issue 3, No 5, 740-753

Abstract: Abstract A graph $$G=(V,E)$$ G = ( V , E ) with even number vertices is called Pfaffian if it has a Pfaffian orientation, namely it admits an orientation such that the number of edges of any M-alternating cycle which have the same direction as the traversal direction is odd for some perfect matching M of the graph G. In this paper, we obtain a necessary and sufficient condition of Pfaffian graphs in a type of bipartite graphs. Then, we design an $$O(|E(G)|^2)$$ O ( | E ( G ) | 2 ) algorithm for recognizing Pfaffian graphs in this class and constructs a Pfaffian orientation if the graph is Pfaffian. The results improve and generalize some known results.

Keywords: Pfaffian orientation; Perfect matching; Bipartite graph; Algorithm (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-017-0207-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:35:y:2018:i:3:d:10.1007_s10878-017-0207-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-017-0207-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().