Analysis and Calculation of Odd Cycle Centrality Aimed for Vertex-Cover

DOI

10.2991/esac-15.2015.58How to use a DOI?

Keywords

Centrality, Minimum vertex cover, MAX-2-XORSAT, Random walk

Abstract

We propose a kind of centrality, the odd cycle centrality which has strong relationship with solving minimum vertex-cover. The formal definition of the odd cycle centrality with its comparison to other centralities is given. Besides, as a variant of MAX-2-XORSAT, it is analyzed in the viewpoint of solving linear equations set. To calculate this centrality and view its effect on different graph structures, a random-walk based method is built to realize the centrality of each node on random graphs and scale-free networks. Using the importance order such as centrality provides one way to understand the topological structure or functions of a network, and it also offers a new viewpoint to solve the constraint satisfaction problems and recognize their complexity.

Copyright

© 2015, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Ting Wang
AU  - Wei Wei
PY  - 2015/08
DA  - 2015/08
TI  - Analysis and Calculation of Odd Cycle Centrality Aimed for Vertex-Cover
BT  - Proceedings of the 2015 International Conference on Electronic Science and Automation Control
PB  - Atlantis Press
SP  - 234
EP  - 237
SN  - 2352-538X
UR  - https://doi.org/10.2991/esac-15.2015.58
DO  - 10.2991/esac-15.2015.58
ID  - Wang2015/08
ER  -