Abstract | ||
---|---|---|
In this paper, we define and investigate the properties of k-Gabriel graphs and also propose an algorithm to construct the k-Gabriel graph of a points set in O(k
2
nlogn) time. The k-Gabriel graphs are also used to improve the running time of solving the Euclidean bottleneck biconnected edge subgraph problem from O(n
2) to 0(nlogn), and that of solving the Euclidean bottleneck matching problem from O(n
2) to O(n
1.5
log
0.5
n). |
Year | DOI | Venue |
---|---|---|
1990 | 10.1007/3-540-52921-7_56 | SIGAL International Symposium on Algorithms |
Keywords | Field | DocType |
k-gabriel graph,k-gabriel graphs | Bottleneck,Graph,Combinatorics,Line graph,Computer science,Euclidean geometry | Conference |
Volume | ISBN | Citations |
450 | 3-540-52921-7 | 20 |
PageRank | References | Authors |
2.19 | 12 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tung-Hsin Su | 1 | 38 | 5.09 |
Ruei-Chuan Chang | 2 | 267 | 56.19 |