Loading...

Please use this identifier to cite or link to this item:
http://nthur.lib.nthu.edu.tw/dspace/handle/987654321/80791

Title:  20Relative Neighborhood Graphs Are Hamiltonian 
Authors:  Chang, M. S.;Tang, C. Y.;Lee, R. C. T. 
Teacher:  李家同 
Date:  1991 
Publisher:  WileyBlackwell 
Relation:  JOURNAL OF GRAPH THEORY, WileyBlackwell, Volume 15, Issue 5, NOV 1991, Pages 543557 
Keywords:  Hamiltonian 
Abstract:  For any two points p and q in the Euclidean plane, define LUN(pq) = {upsilon\upsilon) isanelementof R2, d(pupsilon) < d(pq) and d(qupsilon) < d(pq)}, where d(uupsilon) is the Euclidean distance between two points u and upsilon. Given a set of points V in the plane, let LUN(pq)(V) = V or LUN(pq). Toussaint defined the relative neighborhood graph of V, denoted by RNG(V) or simply RNG, to be the undirected graph with vertices V such that for each pair p,q isanelementof V, (p,q) is an edge of RNG(V) if and only if LUN(pq)(V) = phi. The relative neighborhood graph has several applications in pattern recognition that have been studied by Toussaint. We shall generalize the idea of RNG to define the krelative neighborhood graph of V, denoted by kRNG(V) or simply kRNG, to be the undirected graph with vertices V such that for each pair p,q isanelementof V, (p,q) is an edge of kRNG(V) if and only if \LUN(pq)(V)\ < k, for some fixed positive number k. It can be shown that the number of edges of a kRNG is less than O(kn). Also, a kRNG can be constructed in O(kn2) time. Let E(c) = {e(pq\p isanelementof V and q isanelementof V}. Then G(c) = (V,E(c)) is a complete graph. For any subset F of E(c), define the maximum distance of F as max(e)pq isanelementof F)d(pq). A Euclidean bottleneck Hamiltonian cycle is a Hamiltonian cycle in graph G(c) whose maximum distance is the minimum among all Hamiltonian cycles in graph G(c). We shall prove that there exists a Euclidean bottleneck Hamiltonian cycle which is a subgraph of 20RNG(V). Hence, 20RNGs are Hamiltonian. 
Relation Link:  http://as.wiley.com/WileyCDA/Brand/id35.html 
URI:  http://nthur.lib.nthu.edu.tw/dspace/handle/987654321/80791 
Appears in Collections:  [Lee, Richard ChiaTung (19931994)] LRCT Journal / Magazine Articles [Department of Computer Science] CS Journal / Magazine Articles

Files in This Item:
File 
Size  Format  
index.html  0Kb  HTML  900  View/Open 

在NTHUR中所有的資料項目都受到原著作權保護，僅提供學術研究及教育使用，敬請尊重著作權人之權益。若須利用於商業或營利，請先取得著作權人授權。
若發現本網站收錄之內容有侵害著作權人權益之情事，請權利人通知本網站管理者(smluo@lib.nthu.edu.tw)，管理者將立即採取移除該內容等補救措施。


與系統管理員聯絡

