David Eppstein - Publications

SIAM Journal on Computing

• Reset sequences for monotonic automata.
  D. Eppstein.
  15th Int. Coll. Automata, Languages and Programming, Tampere, Finland, 1988.
  Lecture Notes in Comp. Sci. 317, 1988, pp. 230-238.
  SIAM J. Computing 19(3):500-510, 1990.

  Automata theory. A reset sequence for a DFA is an input such that, no matter which state the DFA starts in, it ends up after the input in a known state. These have been used by Natarajan and Goldberg for certain robot motion planning problems (in fact the conference version of this paper used the title "Reset sequences for finite automata with application to design of parts orienters"), and also in coding theory where they arise in the design of self-synchronizing codes. This paper considers DFAs in which the transition functions respect a given cyclic ordering of the states, and shows that their shortest reset sequences can be found quickly. It also considers parallel algorithms for the problem. There remains open a gap between n² and n³ in the maximum length of reset sequences for general automata.

  (BibTeX -- Citations -- CiteSeer -- ACM DL (ICALP) -- ACM DL (SJC))

• Separator based sparsification II: edge and vertex connectivity.
  D. Eppstein, Z. Galil, G.F. Italiano, and T. Spencer.
  Tech. Rep. CS96-13, Univ. Ca' Foscari di Venezia, Oct. 1996.
  SIAM J. Computing 28(1):341-381, 1999.

  Second half of journal version of Separator based sparsification for dynamic planar graph algorithms.

  (Citations -- ACM DL)

• Finding the k shortest paths.
  D. Eppstein.
  35th IEEE Symp. Foundations of Comp. Sci., Santa Fe, 1994, pp. 154-165.
  Tech. Rep. 94-26, ICS, UCI, 1994.
  SIAM J. Computing 28(2):652-673, 1998.

  Finds multiple short paths connecting two terminals in a graph (allowing repeated vertices and edges in the paths) in constant time per path after a preprocessing stage dominated by a single-source shortest path computation. Applications include dynamic programs for the knapsack problem, biological sequence alignment, and maximum inscribed polygons.

  (BibTeX -- Full paper -- Citations -- Graehl implementation -- Jiménez-Marzal implementations -- Shibuya implementation -- Martins implementation -- CiteSeer: TR '94, SJC '98 -- ACM DL)

• Setting parameters by example.
  D. Eppstein.
  arxiv:cs.DS/9907001.
  40th IEEE Symp. Foundations of Comp. Sci., 1999, pp. 309-318.
  SIAM J. Computing 32(3):643-653, 2003.

  We introduce a class of "inverse parametric optimization" problems, in which one is given both a parametric optimization problem and a desired optimal solution; the task is to determine parameter values that lead to the given solution. We use low-dimensional linear programming and geometric sampling techniques to solve such problems for minimum spanning trees, shortest paths, and other optimal subgraph problems, and discuss applications in multicast routing, vehicle path planning, resource allocation, and board game programming.

  (BibTeX -- Citations -- ACM DL (FOCS) -- ACM DL (SJC))

• Improved combinatorial group testing for real-world problem sizes.
  D. Eppstein, M. T. Goodrich, and D. S. Hirschberg.
  9th Worksh. Algorithms and Data Structures, Waterloo, 2005.
  Lecture Notes in Comp. Sci. 3608, 2005, pp. 86-98.
  arxiv:cs.DS/0505048.
  SIAM J. Computing 36(5):1360-1375, 2007.

  We study practically efficient methods for finding few flawed items among large sets of items, by testing whether there exist flaws in each of a small number of batches of items.

  (BibTeX -- Mike's WADS talk slides)

Journals -- Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine

Semi-automatically filtered from a common source file.