Given a sequence of edge insertions and deletions in a graph, finds the corresponding sequence of minimum spanning tree changes, in logarithmic time per update. Similarly solves the planar geometric version of the problem (using a novel "mixed MST" formulation in which part of the input is a graph and part is a point set) in time O(log2 n) for the Euclidean metric and O(log n log log n) for the rectilinear metric.
(BibTeX -- Citations -- CiteSeer -- ACM DL (JA))
A parallelization of the quadtree constructions in "Provably good mesh generation", in an integer model of computation, based on a technique of sorting the input points using values formed by shuffling the binary representations of the coordinates. A side-effect is an efficient construction for the "fair split tree" hierarchical clustering method used by Callahan and Kosaraju for various nearest neighbor problems.
(BibTeX -- CiteSeer -- Citations -- ACM DL)
We show how to find shortest paths along the segments of an arrangement of n vertical and horizontal line segments in the plane, in time O(n3/2).
(BibTeX -- Citations -- CiteSeer -- ACM DL)
We show that any graph can be colored in time O(2.415n), by a dynamic programming procedure in which we extend partial colorings on subsets of the vertices by adding one more color for a maximal independent set. The time bound follows from limiting our attention to maximal independent subsets that are small relative to the previously colored subset, and from bounding the number of small maximal independent subsets that can occur in any graph.
(BibTeX -- Citations -- CiteSeer -- WADS talk slides -- ACM DL)
We give linear-time quasiconvex programming algorithms for finding a Möbius transformation of a set of spheres in a unit ball or on the surface of a unit sphere that maximizes the minimum size of a transformed sphere. We can also use similar methods to maximize the minimum distance among a set of pairs of input points. We apply these results to vertex separation and symmetry display in spherical graph drawing, viewpoint selection in hyperbolic browsing, and element size control in conformal structured mesh generation.
(BibTeX -- Citations -- CiteSeer -- WADS talk slides -- ACM DL)
We use the ellipsoid method to develop (theoretically) efficient algorithms for optimizing linear functions on intersections of zonotopes, and show how to apply this to train soft-margin support vector classifiers.
(BibTeX -- Citations -- CiteSeer -- WADS talk slides -- ACM DL)
We find improved exponential-time algorithms for exact solution of the traveling salesman problem on graphs of maximum degree three and four. We also consider related problems including counting the number of Hamiltonian cycles in such graphs.
(BibTeX -- WADS talk slides -- Citations)
We study practically efficient methods for finding few flawed items among large sets of items, by testing whether there exist flaws in each of a small number of batches of items.
(BibTeX -- Mike's WADS talk slides)
We show how to solve several versions of the problem of casing graph drawings: that is, given a drawing, choosing to draw one edge as upper and one lower at each crossing in order to improve the drawing's readability.
We consider data structures for handling streams of check-in and check-out requests, and that must identify the set of check-ins that are not matched by a corresponding check-out. We show that, if this set has size k, it is possible to handle this problem in space O(k log n) by a deterministic data structure. However, if check-outs may occur that do not match any check-in, then no low-space deterministic solution is possible; instead, we provide a randomized solution with near-optimal space and high probability of answering queries correctly.
Conferences -- Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine
Semi-automatically filtered from a common source file.