SIAM Journal on Computing
I was on the editorial board from 1995 to 2004.- Reset sequences for monotonic automata.
D. Eppstein.
15th Int. Coll. Automata, Languages and Programming, Tampere, Finland, 1988.
Springer, 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 n2 and n3 in the maximum length of reset sequences for general automata.
- 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.
- 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.This paper presents an algorithm that 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. The paths it finds are the k shortest in the graph, where k is a parameter given as input to the algorithm.
The k shortest paths problem has many important applications for finding alternative solutions to geographic path planning problems, network routing, hypothesis generation in computational linguistics, and sequence alignment and metabolic pathway finding in bioinformatics. Although there have been many papers on the k shortest paths problem before and after this one, it has become frequently cited in those application areas. Additionally, it marks a boundary in the theoretical study of the problem: prior theoretical work largely concerned how quickly the problem could be solved, a line of research that was closed off by the optimal time bounds of this paper. Subsequent work has focused instead on devising efficient algorithms for more complex alternative formulations of the problem that avoid the repeated vertices and other shortcomings of the alternative paths produced by this formulation.
The journal version also includes material from a separate 1995 technical report, "Finding common ancestors and disjoint paths in DAGs".
(Full paper – Graehl implementation – Jiménez-Marzal implementations – Shibuya implementation – Martins implementation – Cliff OpenStreetMap demo)
- 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.
- 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.
Springer, 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.
- Linear-time algorithms for geometric graphs with sublinearly many
crossings.
D. Eppstein, M. T. Goodrich, and D. Strash.
arXiv:0812.0893.
20th ACM-SIAM Symp. Discrete Algorithms, New York, 2009, pp. 150–159.
SIAM J. Computing 39 (8): 3814–3829, 2010.If a connected graph corresponds to a set of points and line segments in the plane, in such a way that the number of crossing pairs of line segments is sublinear in the size of the graph by an iterated-log factor, then we can find the arrangement of the segments in linear time. It was previously known how to find the arrangement in linear time when the number of crossings is superlinear by an iterated-log factor, so the only remaining open case is when the number of crossings is close to the size of the graph.
- Area-universal and constrained rectangular layouts.
D. Eppstein, E. Mumford, B. Speckmann, and K. Verbeek.
SIAM J. Computing 41 (3): 537–564, 2012.A combined journal version of "Area-universal rectangular layouts" and "Orientation-constrained rectangular layouts".
- NC algorithms for perfect matching and maximum flow in
one-crossing-minor-free graphs.
D. Eppstein and V. V. Vazirani.
arXiv:1802.00084.
Proc. 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2019), Phoenix, Arizona, 2019, pp. 23–30.
SIAM J. Computing 50 (3): 1014–1033, 2021.We extend Anari and Vazirani's parallel algorithm for perfect matching in planar graphs to the graph families with a forbidden minor with crossing number one, by developing a concept of mimicking networks for perfect matching.
(Slides)