Searching Isomorphic Graphs
Journal Title: Transactions on Networks and Communications - Year 2017, Vol 5, Issue 5
Abstract
To determine that two given undirected graphs are isomorphic, we construct for them auxiliary graphs, using the breadth-first search. This makes capability to position vertices in each digraph with respect to each other. If the given graphs are isomorphic, in each of them we can find such positionally equivalent auxiliary digraphs that have the same mutual positioning of vertices. Obviously, if the given graphs are isomorphic, then such equivalent digraphs exist. Proceeding from the arrangement of vertices in one of the digraphs, we try to determine the corresponding vertices in another digraph. As a result we develop the algorithm for constructing a bijective mapping between vertices of the given graphs if they are isomorphic. The running time of the algorithm equal to (), where n is the number of graph vertices.
Authors and Affiliations
Anatoly D. Plotnikov
Keywords
Related Articles
- EP ID EP273962
- DOI 10.14738/tnc.55.3551
- Views 56
- Downloads 0
Performance Evaluation of Multi‐hop Wireless HART Network on a Real‐life Testbed
Advances in WirelessHART standard in industrial control systems have led to performance evaluation and security analysis in both real‐world testbeds as well as in controlled lab environments. We have conducted months‐lon...
Searching Isomorphic Graphs
To determine that two given undirected graphs are isomorphic, we construct for them auxiliary graphs, using the breadth-first search. This makes capability to position vertices in each digraph with respect to each other....
Stochastic Hybrid Dynamic Multicultural Social Networks
In this work, we investigate the cohesive properties of a stochastic hybrid dynamic multi-cultural network under random environmental perturbations. By considering a multi-agent dynamic network, we model a social structu...
Instilling QoS in Wireless Sensor Networks
Wireless Sensor Networks (WSNs) have been a desired choice for monitoring and automatic control of remote and unreachable objects and environments due to their low cost. However, such deployment requires quality-of servi...
Exploiting Cryptocurrency Miners with OSINT Techniques
Collection of intelligence is one of the key elements to organize more sophisticated methods of attacks. Open Source Intelligence (OSINT) is a technique used by attackers for reconnaissance purposes to gather information...