3 citations · 3 across the 2 of their papers we have counts for
5 papers
How to Catch Marathon Cheaters: New Approximation Algorithms for Tracking Paths
Michael T. Goodrich, Siddharth Gupta, Hadi Khodabandeh +1
Given an undirected graph, , and vertices, and in , the tracking paths problem is that of finding the smallest subset of vertices in whose intersection with any $…
Adaptive Exact Learning in a Mixed-Up World: Dealing with Periodicity, Errors and Jumbled-Index Queries in String Reconstruction
Ramtin Afshar, Amihood Amir, Michael T. Goodrich +1
We study the query complexity of exactly reconstructing a string from adaptive queries, such as substring, subsequence, and jumbled-index queries. Such problems have applications,…
Reconstructing Biological and Digital Phylogenetic Trees in Parallel
Ramtin Afshar, Michael T. Goodrich, Pedro Matias +1
In this paper, we study the parallel query complexity of reconstructing biological and digital phylogenetic trees from simple queries involving their nodes. This is motivated from…
Tracking Paths in Planar Graphs
David Eppstein, Michael T. Goodrich, James A. Liu +1
We consider the NP-complete problem of tracking paths in a graph, first introduced by Banik et. al. [3]. Given an undirected graph with a source and a destination , find the…
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…