Earticle

초록

영어

This paper establishes a theoretical framework by defining a set of concepts useful for classifying graphs and computing the canonical labeling Cmax(G) of a given undirected graph G, which including the partition tree PartT(G), maximum partition tree MaxPT(G), centre subgraph Cen(G), standard regular sequence SRQ(G), standard maximum regular sequence SMRQ(G), and so on. The implementations of algorithms 1 to 5 show how to calculate them accordingly. The worst time complexities of algorithms 1, 2, 4, and 5 are O(n2) respectively. The time complexity of Algorithm 3 is O(n). By Theorem 3, all leaf nodes of PartT(G) and MaxPT(G) are the regular subgraphs. By Theorem 4 and 5, there exists only one Cen(G) in G. Regular Partition Theorem 6 shows that there exists just one corresponding PartT(G), SRQ(G), MaxPT(G), and SMRQ(G). One can use Classification Theorem 7 to category graphs. Theorem 8 and 9 establish the link between the Cen(G) and the calculation of the first node u1 added into MaxQ(G) corresponding to the canonical labeling Cmax(G) of G. Further, it utilizes the Cen(G) to calculate the first node u1 added into MaxQ(G). The proposed methods can be extended to deal with the directed graphs and weighted graphs.

목차

Abstract
 1. Introduction
 2. Problem Statement
 3. Terminology and Notation
 4. Basic Principle for Computing Cmax(G)
  4.1 Compute Cmax(G) of an undirected graph G
 5. The Relevant Algorithms
 6. Software Implementation
 7. Conclusions and Future Work
 Acknowledgements
 References

키워드

저자

• HAO Jian-Qiang [ State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing, 100876, China, School of Computer Science and Information Engineering, Beijing Technology and Business University, 100048, China ]
• GONG Yun-Zhan [ State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing, 100876, China ]
• Tan Li [ School of Computer Science and Information Engineering, Beijing Technology and Business University, 100048, China ]
• Duan Da-Gao [ School of Computer Science and Information Engineering, Beijing Technology and Business University, 100048, China ]

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  International Journal of Grid and Distributed Computing

• 간기

  격월간

• pISSN

  2005-4262

• 수록기간

  2008~2016

• 십진분류

  KDC 505 DDC 605