72 citations · 218 across the 10 of their papers we have counts for
4 papers · 1 filter
Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku
David Eppstein
We provide a simple linear time transformation from a directed or undirected graph with labeled edges to an unlabeled digraph, such that paths in the input graph in which no two co…
Algorithms for Drawing Media
David Eppstein
We describe algorithms for drawing media, systems of states, tokens and actions that have state transition graphs in the form of partial cubes. Our algorithms are based on two prin…
The lattice dimension of a graph
David Eppstein
We describe a polynomial time algorithm for, given an undirected graph G, finding the minimum dimension d such that G may be isometrically embedded into the d-dimensional integer l…
Quasiconvex Analysis of Backtracking Algorithms
David Eppstein
We consider a class of multivariate recurrences frequently arising in the worst case analysis of Davis-Putnam-style exponential time backtracking algorithms for NP-hard problems. W…