Back to Search
Start Over
Using k-Mix-Neighborhood Subdigraphs to Compute Canonical Labelings of Digraphs
- Source :
- Entropy; Volume 19; Issue 2; Pages: 79, Entropy, Vol 19, Iss 2, p 79 (2017)
- Publication Year :
- 2017
- Publisher :
- MDPI AG, 2017.
-
Abstract
- This paper presents a novel theory and method to calculate the canonical labelings of digraphs whose definition is entirely different from the traditional definition of Nauty. It indicates the mutual relationships that exist between the canonical labeling of a digraph and the canonical labeling of its complement graph. It systematically examines the link between computing the canonical labeling of a digraph and the k-neighborhood and k-mix-neighborhood subdigraphs. To facilitate the presentation, it introduces several concepts including mix diffusion outdegree sequence and entire mix diffusion outdegree sequences. For each node in a digraph G, it assigns an attribute m_NearestNode to enhance the accuracy of calculating canonical labeling. The four theorems proved here demonstrate how to determine the first nodes added into M a x Q ( G ) . Further, the other two theorems stated below deal with identifying the second nodes added into M a x Q ( G ) . When computing C m a x ( G ) , if M a x Q ( G ) already contains the first i vertices u 1 , u 2 , ⋯ , u i , Diffusion Theorem provides a guideline on how to choose the subsequent node of M a x Q ( G ) . Besides, the Mix Diffusion Theorem shows that the selection of the ( i + 1 ) th vertex of M a x Q ( G ) for computing C m a x ( G ) is from the open mix-neighborhood subdigraph N + + ( Q ) of the nodes set Q = { u 1 , u 2 , ⋯ , u i } . It also offers two theorems to calculate the C m a x ( G ) of the disconnected digraphs. The four algorithms implemented in it illustrate how to calculate M a x Q ( G ) of a digraph. Through software testing, the correctness of our algorithms is preliminarily verified. Our method can be utilized to mine the frequent subdigraph. We also guess that if there exists a vertex v ∈ S + ( G ) satisfying conditions C m a x ( G − v ) ⩽ C m a x ( G − w ) for each w ∈ S + ( G ) ∧ w ≠ v , then u 1 = v for M a x Q ( G ) .
- Subjects :
- 0301 basic medicine
k-mix-neighborhood subdigraph
mix diffusion degree sequence
adjacency matrix
General Physics and Astronomy
lcsh:Astrophysics
02 engineering and technology
entire mix diffusion degree sequences
Combinatorics
03 medical and health sciences
lcsh:QB460-466
0202 electrical engineering, electronic engineering, information engineering
canonical labeling
algorithm
Adjacency matrix
lcsh:Science
Complement graph
Mathematics
Discrete mathematics
Digraph
lcsh:QC1-999
Vertex (geometry)
030104 developmental biology
Software testing
lcsh:Q
020201 artificial intelligence & image processing
U-1
lcsh:Physics
Subjects
Details
- ISSN :
- 10994300
- Volume :
- 19
- Database :
- OpenAIRE
- Journal :
- Entropy
- Accession number :
- edsair.doi.dedup.....895517012a11158a3332598217a791fc