article

Free access

The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees

Author:

Kenneth J. SupowitAuthors Info & Claims

Journal of the ACM (JACM), Volume 30, Issue 3

Pages 428 - 448

https://doi.org/10.1145/2402.322386

Published: 01 July 1983 Publication History

PDF eReader

References

[1]

CRemTON, D, AND TAgJA~, R.E.finding minimum spanning trees. Stare J. Comput 5, 4 (Dec. 1976).

Google Scholar

[2]

K~EE, V.On the complexity of d-dimensional Voronoi diagrams. Arch. Math 34 (1980), 75-80.

Google Scholar

[3]

LEE, D.T., AND PREPARATA, F P.The all nearest-neighbor problem for convex polygons, lnf Process. Lett. 7, 4 (June 1978).

Google Scholar

[4]

REINNGOLD, E M., NIEVERGELT, J., AND DEo, N CombmatorJal Algortthms: Theory and Practice. Prentice-Hall, Englewood Chffs, N J, 1977.

Crossref

Google Scholar

[5]

Snx~os, M.I.Computational geometry Dep of Computer Science, Yale Univ., New Haven, Corm, 1978.

Google Scholar

[6]

TOUSSAINT, G.T. The relattve netghborhood graph of a finite planar set Pattern Recogn. 12 (1980), 261-268.

Google Scholar

[7]

Totrss^llcr, G T Comment on "Algorithms for Computing Relative Neighborhood Graph" Eleciron. Lett 16, 22 (Oct 1980).

Google Scholar

[8]

URQUHART, R.B Algorithms for computation of relative neighborhood graph Electron Left 16, 14 (July 1980)

Google Scholar

[9]

YANG, C C, AND LEE, D.T. A note on the all nearest-neighbor problem for convex polygons, lnf Process. Lett 8 (April 1979),

Google Scholar

Cited By

View all

Agrawal SRathi R(2024)Impact and optimization of refresh time in MANETs using FGSSk for topology Control*2024 OPJU International Technology Conference (OTCON) on Smart Computing for Innovation and Advancement in Industry 4.010.1109/OTCON60325.2024.10687651(1-5)Online publication date: 5-Jun-2024
https://doi.org/10.1109/OTCON60325.2024.10687651
Wang JWu YLi SNie F(2023)A self-training algorithm based on the two-stage data editing method with mass-based dissimilarityNeural Networks10.1016/j.neunet.2023.09.046168(431-449)Online publication date: Nov-2023
https://doi.org/10.1016/j.neunet.2023.09.046
Clarkson K(2023)An algorithm for geometric minimum spanning trees requiring nearly linear expected timeAlgorithmica10.1007/BF015539024:1-4(461-469)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF01553902
Show More Cited By

Index Terms

The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Good spanning trees in graph drawing

Introduces a good spanning tree of a plane graph.Solves two open problems on monotone drawings using good spanning trees.Finds a 2-visibility drawing of a planar graph using a good spanning tree.Gives algorithms to find an spike-VPG and T-shaped ...
Balancing minimum spanning trees and multiple-source minimum routing cost spanning trees on metric graphs

Both the building cost and the multiple-source routing cost are important considerations in construction of a network system. A spanning tree with minimum building cost among all spanning trees is called a minimum spanning tree (MST), and a spanning ...
Degree-bounded minimum spanning tree for unit disk graph

Degree-bounded minimum spanning tree (DBMST) has been widely used in many applications of wireless sensor networks, such as data aggregation, topology control, etc. However, before construction of DBMST, it is NP-hard to determine whether or not there ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 30, Issue 3

July 1983

297 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/2402

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1983

Published in JACM Volume 30, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

138
Total Citations
View Citations
2,921
Total Downloads

Downloads (Last 12 months)263
Downloads (Last 6 weeks)34

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Agrawal SRathi R(2024)Impact and optimization of refresh time in MANETs using FGSSk for topology Control*2024 OPJU International Technology Conference (OTCON) on Smart Computing for Innovation and Advancement in Industry 4.010.1109/OTCON60325.2024.10687651(1-5)Online publication date: 5-Jun-2024
https://doi.org/10.1109/OTCON60325.2024.10687651
Wang JWu YLi SNie F(2023)A self-training algorithm based on the two-stage data editing method with mass-based dissimilarityNeural Networks10.1016/j.neunet.2023.09.046168(431-449)Online publication date: Nov-2023
https://doi.org/10.1016/j.neunet.2023.09.046
Clarkson K(2023)An algorithm for geometric minimum spanning trees requiring nearly linear expected timeAlgorithmica10.1007/BF015539024:1-4(461-469)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF01553902
Mwakilama EAli PChidzalo PMtonga KEneya L(2022)On Average Distance of Neighborhood Graphs and Its ApplicationsRecent Applications in Graph Theory10.5772/intechopen.98986Online publication date: 18-May-2022
https://doi.org/10.5772/intechopen.98986
Foster CSevilmis BKimia B(2022)Generalized Relative Neighborhood Graph (GRNG) for Similarity SearchSimilarity Search and Applications10.1007/978-3-031-17849-8_11(133-149)Online publication date: 5-Oct-2022
https://dl.acm.org/doi/10.1007/978-3-031-17849-8_11
Shimomura LOyamada RVieira MKaster D(2020)A survey on graph-based methods for similarity searches in metric spacesInformation Systems10.1016/j.is.2020.101507(101507)Online publication date: Feb-2020
https://doi.org/10.1016/j.is.2020.101507
Schrauth MPortela J(2019)Fast algorithm for topologically disordered lattices with constant coordination numberPhysical Review Research10.1103/PhysRevResearch.1.0330611:3Online publication date: 30-Oct-2019
https://doi.org/10.1103/PhysRevResearch.1.033061
Mathieson LMoscato P(2019)An Introduction to Proximity GraphsBusiness and Consumer Analytics: New Ideas10.1007/978-3-030-06222-4_4(213-233)Online publication date: 31-May-2019
https://doi.org/10.1007/978-3-030-06222-4_4
d’Amore FFranciosa P(2018)A Low Arithmetic-Degree Algorithm for Computing Proximity GraphsInternational Journal of Computational Geometry & Applications10.1142/S021819591850005X28:03(227-253)Online publication date: 15-Nov-2018
https://doi.org/10.1142/S021819591850005X
Götte TScheideler CSetzer A(2018)On Underlay-Aware Self-Stabilizing Overlay NetworksStabilization, Safety, and Security of Distributed Systems10.1007/978-3-030-03232-6_4(50-64)Online publication date: 20-Oct-2018
https://doi.org/10.1007/978-3-030-03232-6_4
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

Good spanning trees in graph drawing

Balancing minimum spanning trees and multiple-source minimum routing cost spanning trees on metric graphs

Degree-bounded minimum spanning tree for unit disk graph

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations