Algorithm for finding one of the largest common subgraphs of two three-dimensional graph structures
✍ Scribed by Sumio Masuda; Hiroyuki Yoshioka; Eiichi Tanaka
- Publisher
- John Wiley and Sons
- Year
- 1998
- Tongue
- English
- Weight
- 176 KB
- Volume
- 81
- Category
- Article
- ISSN
- 1042-0967
No coin nor oath required. For personal study only.
✦ Synopsis
Given two connected graphs G a = (V a , E a ) and G b = (V b , E b ) with three-dimensional structures. Let n a = |V a |, m a = |E a |, n b = |V b |, and m b = |E b |. Let the maxi- mum order of a vertex in G a (G b ) be l a (l b ). Initially this paper offers a method to find a largest common subgraph of G a and G b in O(l a m a 2 l b m b logn b ) time. Then, an algorithm with O(n a 1.5
n b logn a logn b ) time is proposed for the case where G a is a planar structure with a three-dimensional structure and satisfies the following two conditions. Condition 1: In G a and G b , no vertex has order exceeding a specified constant c. Condition 2: In G a , no two adjacent edges are located on the same straight-line. In particular, we show that when G a is a tree, and conditions 1 and 2 are satisfied, a largest common substructure of G a and G b can be found in O (n a n b logn a logn b ) time. ©1998 Scripta Technica, Electron