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

author:

Lin, Fenggen (Lin, Fenggen.) [1] (Scholars:林峰根) | Zhang, Lianzhu (Zhang, Lianzhu.) [2] | Lu, Fuliang (Lu, Fuliang.) [3]

Indexed by:

EI Scopus SCIE

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:

Algorithm Bipartite graph Pfaffian orientation

Community:

  • [ 1 ] [Lin, Fenggen]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou 350108, Fujian, Peoples R China
  • [ 2 ] [Zhang, Lianzhu]Xiamen Univ, Sch Math Sci, Xiamen 361005, Peoples R China
  • [ 3 ] [Lu, Fuliang]Linyi Univ, Sch Sci, Linyi 276000, Shandong, Peoples R China

Reprint 's Address:

  • [Zhang, Lianzhu]Xiamen Univ, Sch Math Sci, Xiamen 361005, Peoples R China

Show more details

Version:

Related Keywords:

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

Online/Total:229/10062510
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