Journal: Algorithmica

Found 758 papers in total
Finding the k shortest paths in parallel
Finding the k shortest paths in parallel
2000,
A concurrent-read exclusive-write PRAM algorithm is developed to find the k shortest...
Improved algorithms for dynamic shortest paths
Improved algorithms for dynamic shortest paths
2000,
We describe algorithms for finding shortest paths and distances in outerplanar and...
The contraction method for recursive algorithms
The contraction method for recursive algorithms
2001,
In this paper we give an introduction to the analysis of algorithms by the contraction...
An analytic approach to the height of binary search trees
An analytic approach to the height of binary search trees
2001,
By using analytic tools it is shown that the expected value of the height H n of...
Fault-tolerant real-time scheduling
Fault-tolerant real-time scheduling
2000,
We use competitive analysis to study how best to use redundancy to achieve...
Parallel approximation algorithms by positive linear programming
Parallel approximation algorithms by positive linear programming
2000,
This note points out and corrects a mistake in the paper ‘Parallel Approximation...
Robot motion planning: A game-theoretic foundation
Robot motion planning: A game-theoretic foundation
2000,
Analysis techniques and algorithms for basic path planning have become quite valuable...
An algorithm for enumerating all spanning trees of a directed graph
An algorithm for enumerating all spanning trees of a directed graph
2000,
We present an O(NV + V³) time algorithm for enumerating all spanning trees...
Near-optimal bounded-degree spanning trees
Near-optimal bounded-degree spanning trees
2001,
Random costs C ( i,j ) are assigned to the area of a complete directed graph on n...
Analysis of an adaptive algorithm to find the two nearest neighbors
Analysis of an adaptive algorithm to find the two nearest neighbors
2001,
Given a set S of N distinct elements in random order and a pivot x is an element of S...
Output-sensitive reporting of disjoint paths
Output-sensitive reporting of disjoint paths
1999,
A k -path query on a graph consists of computing k vertex-disjoint paths between two...
A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
1994,
We give a linear time and space algorithm for analyzing trees in planar graphs. The...
A geometric view of parametric linear programming
A geometric view of parametric linear programming
1992,
We present a new definition of optimality intervals for the parametric right-hand side...
Improved bounds for on-line load balancing
Improved bounds for on-line load balancing
1999,
We consider the following load balancing problem. Jobs arrive on-line and must be...
The seat reservation problem
The seat reservation problem
1999,
We investigate the problem of giving seat reservations on-line. We assume that a train...
Concatenation-based greedy heuristics for the Euclidean Steiner tree problem
Concatenation-based greedy heuristics for the Euclidean Steiner tree problem
1999,
We present a class of O (n log n) heuristics for the Steiner tree problem in the...
On pattern frequency occurrences in a Markovian sequence
On pattern frequency occurrences in a Markovian sequence
1998,
Consider a given pattern H and a random text T generated by a Markovian source. We...
On-line load balancing and network flow
On-line load balancing and network flow
1998,
In this paper we study two problems that can be viewed as on-line games on a dynamic...
Average-case analysis of priority trees: A structure for priority queue administration
Average-case analysis of priority trees: A structure for priority queue administration
1998,
Priority trees (p-trees) are a certain variety of binary trees of size n constructed...
Maintaining spanning trees of small diameter
Maintaining spanning trees of small diameter
1998,
Given a graph G with m edges and n nodes, a spanning tree T of G, and an edge e that...
An O(n log n) average time algorithm for computing the shortest network under a given topology
An O(n log n) average time algorithm for computing the shortest network under a given topology
1999,
In 1992 F.K. Hwang and J.F. Weng published an O(n 2 ) time algorithm for computing the...
Approximate option pricing
Approximate option pricing
1999,
As increasingly large volumes of sophisticated options are traded in world financial...
A risk–reward framework for the competitive analysis of financial games
A risk–reward framework for the competitive analysis of financial games
1999,
Competitive analysis is concerned with minimizing a relative measure of performance....
Competitive optimal on-line leasing
Competitive optimal on-line leasing
1999,
Consider an on-line player who needs some equipment (e.g., a computer) for an...
Papers per page: