3 citations · 7 across the 8 of their papers we have counts for
10 papers
Faster Mixing for Triangulations via Transport Flows
Vedat Levi Alev, Daniel Frishberg, Michail Sarantis +1
We prove an bound for the relaxation time and the log-Sobolev time (inverse log-Sobolev constant) of the classical triangulation flip chain on a convex -…
On the expansion of Hanoi graphs
David Eppstein, Daniel Frishberg, William Maxwell
The famous Tower of Hanoi puzzle involves moving discs of distinct sizes from one of pegs (traditionally ) to another of the pegs, subject to the constraints tha…
Mixing on Generalized Associahedra
William Chang, Colin Defant, Daniel Frishberg
Eppstein and Frishberg recently proved that the mixing time for the simple random walk on the -skeleton of the associahedron is . We obtain similar rapid mixing…
Improved Distributed Algorithms for Random Colorings
Charlie Carlson, Daniel Frishberg, Eric Vigoda
We study distributed versions of Markov Chain Monte Carlo (MCMC) algorithms for generating random -colorings of an input graph with maximum degree . In the sequential setting…
Improved mixing for the convex polygon triangulation flip walk
David Eppstein, Daniel Frishberg
We prove that the well-studied triangulation flip walk on a convex point set mixes in time O(n^3 log^3 n), the first progress since McShine and Tetali's O(n^5 log n) bound in 1997.…
Rapid mixing for the hardcore Glauber dynamics and other Markov chains in bounded-treewidth graphs
David Eppstein, Daniel Frishberg
We give a new rapid mixing result for a natural random walk on the independent sets of a graph . We show that when has bounded treewidth, this random walk -- known as the Gl…
Angles of Arc-Polygons and Lombardi Drawings of Cacti
David Eppstein, Daniel Frishberg, Martha C. Osegueda
We characterize the triples of interior angles that are possible in non-self-crossing triangles with circular-arc sides, and we prove that a given cyclic sequence of angles can be…
On the treewidth of Hanoi graphs
David Eppstein, Daniel Frishberg, William Maxwell
The objective of the well-known Towers of Hanoi puzzle is to move a set of disks one at a time from one of a set of pegs to another, while keeping the disks sorted on each peg. We…
Simplifying Activity-on-Edge Graphs
David Eppstein, Daniel Frishberg, Elham Havvaei
We formalize the simplification of activity-on-edge graphs used for visualizing project schedules, where the vertices of the graphs represent project milestones, and the edges repr…
Euclidean TSP, Motorcycle Graphs, and Other New Applications of Nearest-Neighbor Chains
Nil Mamano, Alon Efrat, David Eppstein +5
We show new applications of the nearest-neighbor chain algorithm, a technique that originated in agglomerative hierarchical clustering. We apply it to a diverse class of geometric…