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 62
- Downloads 0
Whisper: A High Capacity File Encrypting and Hiding Method in an Audio File
The advance of internet and multimedia allows for tremendous transferring of digital media data and the percentage of time that users spend in online activity and exchanging important information is increasing day by day...
An IOT-enabled System for Marine Data Acquisition and Cartography
Current satellite communication remains very expensive and impractical for most small to mid-sized vessels, and at the same time marine wireless networking is lack of network coverage. To solve this problem, this paper p...
Achieving Scalability with Data Owner Anonymity in Cloud Access Control
Cloud computing is a trending technology that enables subscribing organizations to outsource computations and storage, and eliminates the need of purchasing and maintaining the equipment by the organizations themselves....
Seven Cool Number Patterns
Inspired by a number pattern found while reading an online newspaper seven number patterns are created. Behind each pattern there is a distinct algorithm. Some of these patterns are a sequence of a single or double digit...
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...