We apply the nearest-neighbor chain algorithm to repeatedly find pairs of mutual nearest neighbors for different distances, speeding up the times for the multi-fragment TSP heuristic, motorcycle graphs, straight skeletons, and other problems.
Given a partially ordered set of activities, we find in polynomial time a directed acyclic graph and a mapping from activities to its edges, such that the sequences of activities along paths in the graph are exactly the totally ordered subsets of activities in the input.
The n-disc p-peg Hanoi graphs have treewidth within a polynomial factor of np − 1.
We precisely characterize the triples vertex angles that are possible for arc-triangles (curved triangles made from circular arcs), and prove an existence theorem for a large class of sets of angles for arc-polygons. Our characterization allows us to prove that every cactus graph has a planar Lombardi drawing for its natural planar embedding (the embedding in which each cycle is a bounded face), but that there exist other embeddings of cacti that have no Lombardi drawing.
A random walk on the independent sets or dominating sets of a graph mixes rapidly for graphs of bounded treewidth, and a random walk on maximal independent sets mixes rapidly for graphs of bounded carving width.
The associahedron is a polytope whose vertices represent the triangulations of a convex polygon, and whose edges represent flips connecting one triangulation to another. We show that a random walk on the edges of this polytope rapidly converges to the uniform distribution on triangulations. However, we also show that the associahedron does not have constant expansion.
Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine
Semi-automatically filtered from a common source file.