321 citations · 2k across the 200 of their papers we have counts for
64 papers · 1 filter
Layer-Respecting Linear Graph Layouts
Alvin Chiu, David Eppstein, Michael T. Goodrich +1
We show how to visualize a graph, , as a layered drawing, layer-respecting arc diagram, or layer-respecting linear cylindric drawing with a minimum number of edge crossing…
Zip-Tries: Simple Dynamic Data Structures for Strings
David Eppstein, Ofek Gila, Michael T. Goodrich +1
In this paper, we introduce zip-tries, which are simple, dynamic, memory-efficient data structures for strings. Zip-tries support search and update operations for -length string…
Quasipolynomiality of the Smallest Missing Induced Subgraph
David Eppstein, Andrea Lincoln, Virginia Vassilevska Williams
We study the problem of finding the smallest graph that does not occur as an induced subgraph of a given graph. This missing induced subgraph has at most logarithmic size and can b…
Lower Bounds for Non-Adaptive Shortest Path Relaxation
David Eppstein
We consider single-source shortest path algorithms that perform a sequence of relaxation steps whose ordering depends only on the input graph structure and not on its weights or th…
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…
Finding Relevant Points for Nearest-Neighbor Classification
David Eppstein
In nearest-neighbor classification problems, a set of -dimensional training points are given, each with a known classification, and are used to infer unknown classifications of…