BAP: Lecture 9 (Mar 12, 2002)
The notes for this lecture are available in
In this lecture, we
- Discussed models of k-ply neighborhood graphs and well-shaped meshes.
Material for these presentations was drawn from:
- Gary L. Miller, Shang-Hua Teng, William Thurston, and Stephen
A. Vavasis. "Separators for sphere-packings and nearest neighbor
graphs." Journal of the ACM, 44(1):1-29, January 1997.
Gary L. Miller, Shang-Hua Teng, William Thurston, and Stephen A. Vavasis.
"Geometric separators for finite
element meshes." Siam Journal on Scientific Computing, 19(2):364--386, March 1998.
We then presented Turner's analysis of the Cuthill-McKee heuristic
for bandwidth minimization, from:
- Jonathan S. Turner: "On the Probable
Performance of Heuristics for Bandwidth Minimization" in SIAM
J. Comput, Vol 15, No 2, May 1986.