Indexed by:
Abstract:
An even cycle C of a graph G is nice if the graph G - V(C) has a perfect matching. An orientation of G is a Pfaffian orientation if every nice cycle of G has an odd number of edges directed in either direction of the cycle. A graph is Pfaffian if it has a Pfaffian orientation. If a graph is Pfaffian, then the number of perfect matchings of it can be computed in polynomial time. In this paper, we focus on a special type of 1-extendable bipartite graph with maximum degree Delta(G) = vertical bar V(G)vertical bar/2. We characterize some properties of Pfaffian graphs in this type. According to the properties, we find an algorithm in time O(vertical bar E(G)vertical bar(2)) to determine whether a graph G in this type is Pfaffian or not. Furthermore, if G is Pfaffian, this algorithm also constructs a Pfaffian orientation of it. (C) 2014 Elsevier B.V. All rights reserved.
Keyword:
Reprint 's Address:
Email:
Version:
Source :
THEORETICAL COMPUTER SCIENCE
ISSN: 0304-3975
Year: 2014
Volume: 527
Page: 97-101
0 . 6 5 7
JCR@2014
0 . 9 0 0
JCR@2023
ESI Discipline: COMPUTER SCIENCE;
ESI HC Threshold:195
JCR Journal Grade:3
CAS Journal Grade:4
Cited Count:
WoS CC Cited Count: 1
SCOPUS Cited Count: 1
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: