Edge integrity of nearest neighbor graphs and separator theorems
References
[1]
Agarwal P.K., Pach J., Combinatorial Geometry, in: Wiley-Interscience Series in Discrete Math. and Optimization, John Wiley & Sons, Inc., New York, 1995.
[2]
Alon N., Seymour P., Thomas R., Planar separators, SIAM J. Discrete Math. 7 (1994) 184–193.
[3]
Bagga K.S., Beineke L.W., Lipman M.J., Pippert R.E., Edge-integrity: a survey, Discrete Math. 124 (1994) 3–12.
[4]
Bagga K.S., Beineke L.W., Lipman M.J., Pippert R.E., Sedlmeyer R.L., A good algorithm for the computation of the edge-integrity of trees, Congr. Numer. 67 (1988) 225–232.
[5]
Bagga K.S., Beineke L.W., Lipman M.J., Pippert R.E., Sedlmeyer R.L., Some bounds and an algorithm for the edge-integrity of trees, Ars Combin. 35 (1993) 225–238.
[6]
Barefoot C.A., Entriger R., Swart H., Integrity of trees and powers of cycles, in: Eighteenth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL 1987), in: Congr. Numer., vol. 58, 1987, pp. 103–114.
[7]
Barefoot C.A., Entringer R., Swart H., Vulnerability in graphs–a comparative survey, J. Combin. Math. Combin. Comput. 1 (1987) 12–22.
[8]
Benko D., Ernst C., Lanphier D., Asymptotic bounds on the integrity of graphs and separator theorems, SIAM J. Discrete Math. 23 (2009) 265–277.
[9]
Bollobás B., Leader I., Edge-isoperimetric inequalities in the grid, Combinatorica 11 (4) (1991) 299–314.
[10]
Brito M., Chávez E., Quiroz A., Yukich J., Connectivity of the mutual k-nearest neighbor graph in clustering and outlier detection, Statist. Probab. Lett. 35 (1997) 33–42.
[11]
Brownlee J., K-Nearest neighbors for machine learning, Mach. Learn. Algorithms (2016).
[12]
Chamizo F., Iwaniec H., On the sphere problem, Rev. Mat. Iberoam. 11 (2) (1995) 417–429.
[13]
Chávez E., Paredes R., Using the k nearest neighbor graph for proximity searching in metric spaces, in: String Processing and Information Retrieval, in: Lect. Notes in Comp. Sci., vol. 3772, Springer, Berlin, 2005, pp. 127–138.
[14]
Chen J., Fang H.R., Saad Y., Fast approximate k N N graph construction for high dimensional data via recursive Lanczos bisection, J. Mach. Learn. Res. 10 (2009) 1989–2012.
[15]
Chudnov A.M., On minimax signal generation and reception algorithms, Probl. Inform. Transm. 22 (4) (1986) 49–54.
[16]
Diks K., Djidjev H.N., Sýkora O., Vrťo I., Edge separators of planar and outerplanar graphs with applications, J. Algorithms 14 (1993) 258–279.
[17]
Djidjev H.N., A separator theorem for graphs of fixed genus, Serdica Math. J. 11 (1985) 319–329.
[18]
Dunkum M., Lanphier D., Vulnerability of nearest neighbor graphs, Discrete Appl. Math. 171 (2014) 42–52.
[19]
Federer H., Geometric Measure Theory, in: Classic Texts in Math., Springer-Verlag, Berlin Heidelberg, 1996.
[20]
Fränti P., Virmajoki O., Hautamäki V., Fast agglomerative clustering using a k-nearest neighbor graph, IEEE Trans. Pattern Anal. Mach. Intell. 28 (11) (2006) 1875–1881.
[21]
Goddard W., Swart H., Integrity in graphs: bounds and basics, J. Combin. Math. Combin. Comput. 7 (1990) 139–151.
[22]
González-Barrios J.M., Quiroz A.J., A clustering procedure based on the comparison between the k-nearest neighbor graph and the minimal spanning tree, Statist. Prob. Lett. 62 (1) (2003) 23–34.
[23]
Huxley M.N., Exponential sums and lattice points II, Proc. Lond. Math. Soc. 66 (1993) 279–301.
[24]
Kabatyanskil G.A., Levenshtein V.I., On bounds for packings on a sphere and in space, Probl. Inform. Transm. 14 (1) (1978) 1–17.
[25]
Lipton R.J., Tarjan R.E., A separator theorem for planar graphs, SIAM J. Appl. Math. 36 (1979) 177–189.
[26]
Lipton R.J., Tarjan R.E., Applications of a planar separator theorem, SIAM J. Comput. 9 (1980) 615–627.
[27]
Miller G.L., Teng S.-H., Thurston W., Vavasis S.A., Separators for sphere-packings and nearest neighbor graphs, J. ACM 44 (1997) 1–29.
[28]
Miller G.L., Teng S.-H., Thurston W., Vavasis S.A., Geometric separators for finite-element meshes, SIAM J. Sci. Comput. 19 (2) (1998) 364–386.
[29]
Moazzami D., An algorithm for the computation of edge integrity, I ′ ( T ), Int. J. Contemp. Math. Sci. 6 (11) (2011) 507–516.
[30]
Simon H.D., Teng S.-H., How good is recursive bijection?, SIAM J. Sci. Comput. 18 (5) (1997) 1436–1445.
[31]
Smith W.D., Wormald N.C., Geometric separator theorems and applications, in: 39th Annual Symp. on Foundations of Comp. Sci., in: FOCS ’98, 1998, pp. 232–243.
[32]
Sýkora O., Vrťo I., Edge separators for graphs of bounded genus with applications, Theoret. Comput. Sci. 112 (2) (1993) 419–429.
[33]
Tang B., He H., ENN: Extended nearest neighbor method for pattern recognition [Research Frontier], IEEE Comput. Intell. Mag. 10 (3) (2015) 52–60.
[34]
Teng S.-H., Points, Spheres, and Separators, A Unified Geometric Approach to Graph Partitioning, (Ph.D. Thesis) School of Computer Science, Carnegie Mellon University, 1991.
[35]
Toussaint G.T., Geometric proximity graphs for improving nearest neighbor methods in instance-based learning and data mining, Int. J. Comput. Geom. Appl. 15 (2) (2005) 101–150.
Index Terms
- Edge integrity of nearest neighbor graphs and separator theorems
Index terms have been assigned to the content through auto-classification.
Recommendations
Asymptotic Bounds on the Integrity of Graphs and Separator Theorems for Graphs
In this paper we study the integrity of certain graph families. These include planar graphs, graphs with a given genus, graphs on the $d$-dimensional integer lattice $\mathbb{Z}^d$, and graphs that have no $K_h$-minor. We give upper bounds for the ...
On minimal vertex separators of dually chordal graphs: Properties and characterizations
Many works related to dually chordal graphs, their cliques and neighborhoods were published by Brandstadt et al. (1998) [1] and Gutierrez (1996) [6]. We will undertake a similar study by considering minimal vertex separators and their properties ...
Edge-partitions of graphs and their neighbor-distinguishing index
A proper edge coloring is neighbor-distinguishing if any two adjacent vertices have distinct sets consisting of colors of their incident edges. The minimum number of colors needed for a neighbor-distinguishing edge coloring is the neighbor-...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Elsevier B.V.
Publisher
Elsevier Science Publishers B. V.
Netherlands
Publication History
Published: 01 September 2019
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 21 Dec 2024