72 citations · 218 across the 15 of their papers we have counts for
6 papers · 1 filter
Internet Packet Filter Management and Rectangle Geometry
David Eppstein, S. Muthukrishnan
We consider rule sets for internet packet routing and filtering, where each rule consists of a range of source addresses, a range of destination addresses, a priority, and an actio…
Improved Algorithms for 3-Coloring, 3-Edge-Coloring, and Constraint Satisfaction
David Eppstein
We consider worst case time bounds for NP-complete problems including 3-SAT, 3-coloring, 3-edge-coloring, and 3-list-coloring. Our algorithms are based on a constraint satisfaction…
One-Dimensional Peg Solitaire, and Duotaire
Cristopher Moore, David Eppstein
We solve the problem of one-dimensional Peg Solitaire. In particular, we show that the set of configurations that can be reduced to a single peg forms a regular language, and that…
Phutball Endgames are Hard
Erik D. Demaine, Martin L. Demaine, David Eppstein
We show that, in John Conway's board game Phutball (or Philosopher's Football), it is NP-complete to determine whether the current player has a move that immediately wins the game.…
One-Dimensional Peg Solitaire
Cristopher Moore, David Eppstein
We solve the problem of one-dimensional peg solitaire. In particular, we show that the set of configurations that can be reduced to a single peg forms a regular language, and that…
Searching for Spaceships
David Eppstein
We describe software that searches for spaceships in Conway's Game of Life and related two-dimensional cellular automata. Our program searches through a state space related to the…