73 citations · 634 across the 97 of their papers we have counts for
11 papers · 1 filter
Going Off-road: Transversal Complexity in Road Networks
David Eppstein, Michael T. Goodrich, Lowell Trott
A geometric graph is a graph embedded in the plane with vertices at points and edges drawn as curves (which are usually straight line segments) between those points. The average tr…
Randomized Shellsort: A Simple Oblivious Sorting Algorithm
Michael T. Goodrich
In this paper, we describe randomized Shellsort--a simple, randomized, data-oblivious version of the Shellsort algorithm that always runs in O(n log n) time and, as we show, succee…
Efficient Authenticated Data Structures for Graph Connectivity and Geometric Search Problems
Michael T. Goodrich, Roberto Tamassia, Nikos Triandopoulos
Authenticated data structures provide cryptographic proofs that their answers are as accurate as the author intended, even if the data structure is being controlled by a remote unt…
Pipelined Algorithms to Detect Cheating in Long-Term Grid Computations
Michael T. Goodrich
This paper studies pipelined algorithms for protecting distributed grid computations from cheating participants, who wish to be rewarded for tasks they receive but don't perform. W…
The Rainbow Skip Graph: A Fault-Tolerant Constant-Degree P2P Relay Structure
Michael T. Goodrich, Michael J. Nelson, Jonathan Z. Sun
We present a distributed data structure, which we call the rainbow skip graph. To our knowledge, this is the first peer-to-peer data structure that simultaneously achieves high fau…
Improved Adaptive Group Testing Algorithms with Applications to Multiple Access Channels and Dead Sensor Diagnosis
Michael T. Goodrich, Daniel S. Hirschberg
We study group-testing algorithms for resolving broadcast conflicts on a multiple access channel (MAC) and for identifying the dead sensors in a mobile ad hoc wireless network. In…