Wavefront and caustic surfaces of refractive laser beam shaper
David L. Shealy, John A. Hoffnagle
SPIE Optical Engineering + Applications 2007
We first consider the problem of partitioning the edges of a graph G into bipartite cliques such the total order of the cliques is minimized, where the order of a clique is the number of vertices in it. It is shown that the problem is NP-complete. We then prove the existence of a partition of small total order in a sufficiently dense graph and devise an efficient algorithm to compute such a partition and the running time. Next, we define the notion of a compression of a graph G and use the result on graph partitioning to efficiently compute an optimal compression for graphs of a given size. An interesting application of the graph compression result arises from the fact that several graph algorithms can be adapted to work with the compressed representation of the input graph, thereby improving the bound on their running times, particularly on dense graphs. This makes use of the trade-off result we obtain from our partitioning algorithm. The algorithms analyzed include those for matchings, vertex connectivity, edge connectivity, and shortest paths. In each case, we improve upon the running times of the best-known algorithms for these problems. © 1995 by Academic Press, Inc.
David L. Shealy, John A. Hoffnagle
SPIE Optical Engineering + Applications 2007
Alfred K. Wong, Antoinette F. Molless, et al.
SPIE Advanced Lithography 2000
William Hinsberg, Joy Cheng, et al.
SPIE Advanced Lithography 2010
A. Skumanich
SPIE OE/LASE 1992