• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Lin, Fenggen (Lin, Fenggen.) [1] | Zhang, Lianzhu (Zhang, Lianzhu.) [2] | Lu, Fuliang (Lu, Fuliang.) [3]

Indexed by:

EI

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 Δ(G)=|V(G)|/2. We characterize some properties of Pfaffian graphs in this type. According to the properties, we find an algorithm in time O(|E(G)|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. © 2014 Elsevier B.V. All rights reserved.

Keyword:

Algorithms Graph theory Polynomial approximation

Community:

  • [ 1 ] [Lin, Fenggen]College of Mathematics and Computer Science, Fuzhou University, Fuzhou, Fujian 350108, China
  • [ 2 ] [Zhang, Lianzhu]School of Mathematical Sciences, Xiamen University, Xiamen 361005, China
  • [ 3 ] [Lu, Fuliang]School of Science, Linyi University, Linyi, Shandong 276000, China

Reprint 's Address:

Show more details

Related Keywords:

Related Article:

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 HC Threshold:195

JCR Journal Grade:3

CAS Journal Grade:4

Cited Count:

WoS CC Cited Count:

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:

Online/Total:1418/13876659
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1