SIAM Journal on Computing · 1992 · 66 citations · 12 references
ComputingComputer ScienceAlgorithmsMotion PlanningTransportationCombinatorial OptimizationRoute PlanningTransportation ProblemsVehicle SchedulingMinimum-cost Path ComputationMotion Planning For TransportPolynomial Time ComplexityPolynomial-time AlgorithmsTraveling Salesman Problem
Consider the problem of finding a minimum cost tour to transport a set of objects between the vertices of a tree by a vehicle that travels along the edges of the tree. The vehicle can carry only one object at a time, and it starts and finishes at the same vertex of the tree. It is shown that if objects can be dropped at intermediate vertices along its route and picked up later, then the problem can be solved in polynomial time. Two efficient algorithms are presented for this problem. The first algorithm runs in $O(k + qn)$ time, where n is the number of vertices in the tree, k is the number of objects to be moved, and $q \leq \min \{ k,n \}$ is the number of nontrivial connected components in a related directed graph. The second algorithm runs in $O(k + n\log n)$ time.
12
Bounds on Multiprocessing Timing Anomalies
Ron Graham · SIAM Journal on Applied Mathematics · 1969 · 2.4K citations
Fast Algorithms for Finding Nearest Common Ancestors
Dov Harel, Robert E. Tarjan · SIAM Journal on Computing · 1984 · 1.1K citations
Scheduling with Deadlines and Loss Functions
Robert McNaughton · Management Science · 1959 · 846 citations