Optimal Cheeger cuts and bisections of random geometric graphs

Beardwood, J., Halton, J.H. and Hammersley, J. M. (1959). The shortest path through many points. Proc. Cambridge Philos. Soc

1959

Earlier work this paper cites.

Cheeger, J. (1970). A lower bound for the smallest eigenvalue of the Laplacian. Problems in analysis (Papers dedicated to Salomon Bochner, 1969)

1969

Earlier work this paper cites.

Buser, P. (1982). A note on the isoperimetric constant. Ann. Sci. École Norm. Sup. (4)

1982

Earlier work this paper cites.

Bhatt, S.N. and Leighton, F.T. (1984). A framework for solving VLSI graph layout problems. J. Comput. System Sci

1984

Earlier work this paper cites.

Leighton, T., Shor, P. (1989) Tight bounds for minimax grid matching with applications to the average case analysis of algorithms. Combinatorica

1989

Earlier work this paper cites.

Shor, P. W. and Yukich, J. E. (1991). Minimax grid matching and empirical measures. Ann. Probab

1991

Earlier work this paper cites.

Diekmann, R., Monien, B., Preis, R. (1995). Using helpful sets to improve graph bisections. Interconnection networks and mapping and scheduling parallel computations

1995

Earlier work this paper cites.

Chung, F.R.K. (1997) Spectral Graph Theory

1997

Earlier work this paper cites.

Penrose, M.D. (1997). The longest edge of the random minimal spanning tree. Ann. Appl. Probab

1997

Earlier work this paper cites.

Braides, A. (1998). Approximation of Free-Discontinuity Problems

1998

Earlier work this paper cites.

Billingsley, P. (1999). Convergence of Probability Measures

1999

Cited alongside, same era.

Penrose, M.D. (2000) Vertex ordering and partitioning problems for random spatial graphs. Ann. Appl. Probab

2000

Cited alongside, same era.

Díaz, J., Penrose, M.D., Petit, J. and Serna, M. (2001). Approximating layout problems on random geometric graphs. J. Algorithms

2001

Cited alongside, same era.

Benjamini, I. and Mossel, E. (2003). On the mixing time of a simple random walk on the super critical percolation cluster. Probab. Theory Relat. Fields

2003

Cited alongside, same era.

Penrose, M. (2003) Random Geometric Graphs

2003

Cited alongside, same era.

Henrot, A. and Pierre, M. (2005) Variation et Optimisation de Formes. Une Analyse Géométrique

Caselles, V., Chambolle, A. and Novaga, M. (2010) Some remarks on uniqueness and regularity of Cheeger sets. Rend. Semin. Mat. Univ. Padova

2010

Later among the works it cites.

Edelsbrunner, H. and Harer, J.L. (2010). Computational topology. An introduction. American Mathematical Society, Providence, RI

2010

Later among the works it cites.

Arias-Castro, E., Pelletier, B. and Pudlo, P. (2012). The normalized graph cut and Cheeger constant: from discrete to continuous. Adv. Appl. Probab

2012

Later among the works it cites.

Kahle, M. (2014). Topology of random simplicial complexes: a survey. Algebraic topology: applications and new directions

2014

Later among the works it cites.

García Trillos, N. and Slepcev, D. (2015). On the rate of convergence of empirical measures in ∞ \infty -transportation distance. Canad. J. Math

2015

Later among the works it cites.