Back to Search
Start Over
Scott : A method for representing graphs asrooted trees for graph canonization
- Source :
- COMPLEX NETWORKS 2019, COMPLEX NETWORKS 2019, Springer, pp.578-590, 2019, Studies in Computational Intelligence Series, ⟨10.1007/978-3-030-36687-2_48⟩, Complex Networks and Their Applications VIII ISBN: 9783030366865, COMPLEX NETWORKS (1)
- Publication Year :
- 2019
- Publisher :
- HAL CCSD, 2019.
-
Abstract
- International audience; Graphs increasingly stand out as an essential data structurein the field of data sciences. To study graphs, or sub-graphs, that char-acterize a set of observations, it is necessary to describe them formally,in order to characterize equivalence relations that make sense in thescope of the considered application domain. Hence we seek to define acanonical graph notation, so that two isomorphic (sub) graphs have thesame canonical form. Such notation could subsequently be used to indexand retrieve graphs or to embed them efficiently in some metric space.Sequential optimized algorithms solving this problem exist, but do notdeal with labeled edges, a situation that occurs in important applicationdomains such as chemistry. We present in this article a new algorithmbased on graph rewriting that provides a general and complete solution tothe graph canonization problem. Although not reported here, the formalproof of the validity of our algorithm has been established. This claim isclearly supported empirically by our experimentation on synthetic com-binatorics as well as natural graphs. Furthermore, our algorithm supportsdistributed implementations, leading to efficient computing perspectives.
- Subjects :
- graph isomorphism
Graph rewriting
graph canonization
Theoretical computer science
graph rewriting
labeled graph
Computer science
010102 general mathematics
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
0102 computer and information sciences
Data structure
Notation
01 natural sciences
Graph canonization
Formal proof
Metric space
010201 computation theory & mathematics
[INFO.INFO-IR]Computer Science [cs]/Information Retrieval [cs.IR]
Canonical form
0101 mathematics
Graph isomorphism
MathematicsofComputing_DISCRETEMATHEMATICS
Subjects
Details
- Language :
- English
- ISBN :
- 978-3-030-36686-5
- ISBNs :
- 9783030366865
- Database :
- OpenAIRE
- Journal :
- COMPLEX NETWORKS 2019, COMPLEX NETWORKS 2019, Springer, pp.578-590, 2019, Studies in Computational Intelligence Series, ⟨10.1007/978-3-030-36687-2_48⟩, Complex Networks and Their Applications VIII ISBN: 9783030366865, COMPLEX NETWORKS (1)
- Accession number :
- edsair.doi.dedup.....5d90a44b90ced793144f281efc68d711