David Eppstein

*Proc. 35th Symp. Foundations of Computer Science*, IEEE, Nov 1994, pp. 154–165

*SIAM J. Computing* 28(2):652–673, 1998

Tech. report 94-26, Univ. of California, Irvine, Dept. of Information and Computer Science, 1994

*Mathematical Reviews* 99h:05073

http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-94-26.pdf

http://dx.doi.org/10.1137/S0097539795290477

Cited by:

- On finding single-source single-destination $k$ shortest paths
- Parallel Algorithms for the $k$ Shortest Paths and Related Problems
- Enumerating suboptimal alignments of multiple biological sequences efficiently
- New flexible approaches for multiple sequence alignment
- Finding a realistic detour by AI search techniques
- Detour queries in geographical databases for navigation and related algorithm animations
- Optimizing systems for effective block-processing: the $k$-delay problem
- Machine transliteration
- On the $K$-best mode in computer chess: measuring the similarity of move proposals
- Computing strictly-second shortest paths
- Counting the number of paths in a graph via BDDs
- Finding the $k$ shortest paths in parallel
- New Approaches to Flexible Alignment of Multiple Biological Sequences
- 2-best solutions under distance constraints: the model and exemplary results for matroids
- $k$-best solutions under distance constraints in valuated $\Delta$-matroids
- Finding useful detours in geographical databases
- Routing in LEO-based satellite networks.
- An efficient multi-path forwarding method
- Enhanced hypertext categorization using hyperlinks
- Deviation algorithms for ranking shortest paths
- An efficient implementation of an algorithm for finding $K$ shortest simple paths
- A $K$-best paths algorithm for highly reliable communication networks
- Algorithms for shortest paths and $d$-cycle problems
- Dealing with additional constraints in the $k$-shortest path problem
- Metabolic reconstruction using shortest paths
- Translation with finite-state devices
- Computing the $K$ shortest paths: A new algorithm and an experimental comparison
- Automated metabolic reconstruction at the molecular level
- Graph modeling of metabolism
- The first $K$ minimum cost paths in a time-schedule network
- A class of label-correcting methods for the $K$ shortest paths problem
- A randomized algorithm for finding a path subject to multiple QoS requirements
- A*Prune: An algorithm for finding $K$ shortest paths subject to multiple constraints
- Selective flooding for improved quality-of-service routing
- Unified approach to fuzzy graph problems
- Static versus dynamic establishment of protection paths in WDM networks
- Finding the $k$ shortest simple paths: a new algorithm and its implementation
- Semiring frameworks and algorithms for shortest-distance problems
- Time analysis for planning in a time-window network a path
- Phonetic alignment and similarity
- Minimum-cost QoS multicast and unicast routing in communication networks
- On the difficulty of some shortest path problems
- Edge distributed admission control for performance improvement in traffic engineered networks
- Quality of service provisioning through traffic engineering with applicability to IP-based production networks
- Solving biobjective combinatorial max-ordering problems by ranking methods and a two-phases approach
- Multipath routing to provide quality of service in mobile ad hoc networks
- An efficient algorithm for finding a path subject to two additive constraints
- Path computation for traffic engineering in MPLS networks
- Solving some lexicographic multi-objective combinatorial problems
- Topological design and lightpath routing in WDM mesh networks: A combined approach
- An efficient algorithm for sequential generation of failure states in a network with multi-mode components
- New computational approaches for de novo peptide sequencing from MS/MS experiments
- Efficient implementations of a delay-constrained least-cost multicast algorithm
- Modeling costs of turns in route planning
- Genetic algorithms for rerouting shortest paths in dynamic and stochastic networks
- Heuristic and exact algorithms for QoS routing with multiple constraints
- Uncoupled method for equilibrium-based linear path flow estimator for origin-destination trip matrices
- Edge distributed admission control in MPLS networks
- A new traffic engineering manager for DiffServ/MPLS networks: design and implementation on an IP QoS Testbed
- Coordinated target assignment and intercept for unmanned air vehicles
- Multiple additively constrained path selection
- LVMSR: an efficient algorithm to multicast layered video
- A enumeração dos $K$ trajectos mais curtos
- A new improvement for a $K$ shortest paths algorithm
- BANANAS: an evolutionary framework for explicit and multipath routing in the internet
- An efficient algorithm for the $N$-best-strings problem
- Automatisches Generieren von Wanderrouten
- Route specifications with a linear dual graph
- Multiple path QoS routing
- Alternative paths vs. inaccurate link state information in realistic network topologies
- Qualitative link state dissemination control in QoS routing
- Algorithms for Language Reconstruction
- Resource constrained shortest paths
- List detection for multi-access channels
- List detection for symmetric multi-access channels
- PHAROAH, a Beam Search Decoder for Phrase-Based Statistical Machine Translation Models: User Manual and Description
- Noun Phrase Translation
- Fault tolerance and load balancing in QoS provisioning with multiple MPLS paths
- Multi-constrained optimal path selection
- Vickrey prices and shortest paths: what is an edge worth?
- Optimization system in networks using ACO
- Traffic engineering techniques and algorithms for the internet
- Appia: formalization of its topology assignment problem
- Distributed optimal admission controllers for service level agreements in interconnected networks
- Parametric alignment of multiple biological sequences
- Improving back-transliteration by combining information sources
- A lazy version of Eppstein's $K$ shortest paths algorithm
- Autonomous vehicle technologies for small fixed wing UAVs
- Experimental demonstration of multiple robot cooperative target intercept
- Multiple UAV cooperative search under collision avoidance and limited range communication constraints
- Routing and wavelength assignment in single hop all optical networks with minimum blocking
- The shortest path problem with forbidden paths
- In silico atomic tracing by substrate-product relationships in Escherichia coli intermediary metabolism
- Design of wavelength-routed optical network topologies to minimise lightpath blocking probabilities
- An exact algorithm for the robust shortest path problem with interval data
- Routing reliability analysis of partially disjoint paths
- A new algorithm to compute alternate paths in reliable OSPF (ROSPF)
- Optimal admission controllers for service level agreements in enterprise networks
- Reliable routing in MPLS networks
- Bi-directional search in QoS routing
- A decoupled GLS-based path flow estimator for inferring origin-destination matrices
- Policy-driven traffic engineering for intra-domain quality of service provisioning
- Simulation of automatic switched optical transport networks
- Evaluation of novel resilience schemes in dynamic optical transport networks
- Know why your access was denied: regulating feedback for usable security
- Finding the K shortest hyperpaths: algorithms and applications
- Finding the shortest path for quality assurance of electric components
- Shortest paths in chemical kinetic applications
- Route Choice in Stochastic Time-Dependent Networks: Theory, Algorithms and Computational Experience
- Heuristic methods for delay-constrained least cost routing problem using $k$-shortest-path algorithms
- Tosiaikainen ajoneuvoliikenteen reitinsuunnittelu (real-time vehicle traffic route planning)
- SPeCRA: a stochastic performance comparison routing algorithm for LSP setup in MPLS networks
- A new algorithm for $K$ shortest paths problem
- From hierarchies to heterarchies: application of network optimization to design of organizational structures
- On the generation of alternative solutions for discrete optimization problems with uncertain data: an experimental analysis of the penalty method
- Quality of service provisioning for supporting premium services in IP networks
- Selective Flooding for Better QoS Routing
- Viking: a multi-spanning-tree ethernet architecture for metropolitan area and cluster networks
- An algorithm for calculating the $K$ most reliable disjoint paths with a maximum number of arcs
- Routing and wavelength assignment of scheduled lightpath demands in a WDM optical transport network
- Routing and wavelength assignment of scheduled lightpath demands
- Diverse routing of scheduled lightpath demands in an optical transport network
- Dynamical Configuration of Transparent Optical Telecommunication Networks
- Global mapping of nucleic acid conformational space: dinucleoside monophosphate conformations and transition pathways among conformational classes
- On the $k$-simple shortest paths problem in weighted directed graphs
- Cheap labor can be expensive