Journal: Algorithmica

Found 758 papers in total
Static Frequency Assignment in Cellular Networks
Static Frequency Assignment in Cellular Networks
2001,
A cellular network is generally modeled as a subgraph of the triangular lattice. In...
The Dense k ‐Subgraph Problem
The Dense k ‐Subgraph Problem
2001,
This paper considers the problem of computing the dense k ‐vertex subgraph of a...
Ancient and New Algorithms for Load Balancing in the lp Norm
Ancient and New Algorithms for Load Balancing in the lp Norm
2001,
We consider the on‐line load balancing problem where there are m identical...
On Two Class‐Constrained Versions of the Multiple Knapsack Problem
On Two Class‐Constrained Versions of the Multiple Knapsack Problem
2001,
We study two variants of the classic knapsack problem, in which we need to place items...
A Randomized Algorithm for Approximate String Matching
A Randomized Algorithm for Approximate String Matching
2001,
We give a randomized algorithm in deterministic time O(N log M) for estimating the...
Efficient Parallel Computation of the Characteristic Polynomial of a Sparse, Separable Matrix
Efficient Parallel Computation of the Characteristic Polynomial of a Sparse, Separable Matrix
2001,
This paper is concerned with the problem of computing the characteristic polynomial of...
Simple Algorithms for Multimessage Multicasting with Forwarding
Simple Algorithms for Multimessage Multicasting with Forwarding
2001,
We consider multimessage multicasting over the n processor complete (or fully...
Parallel Algorithms for Series Parallel Graphs and Graphs with Treewidth Two
Parallel Algorithms for Series Parallel Graphs and Graphs with Treewidth Two
2001,
In this paper a parallel algorithm is given that, given a graph G=(V,E) , decides...
Algorithms for the On‐Line Travelling Salesman
Algorithms for the On‐Line Travelling Salesman
2001,
In this paper the problem of efficiently serving a sequence of requests presented in...
Equivalence of e ‐Approximate Separation and Optimization in Fixed Dimensions
Equivalence of e ‐Approximate Separation and Optimization in Fixed Dimensions
2001,
Given a closed, convex set X\subseteq \bbR n , containing the origin, we consider the...
Efficient Algorithms for Integer Programs with Two Variables per Constraint
Efficient Algorithms for Integer Programs with Two Variables per Constraint
2001,
Integer programs with m constraints, each with two variables, we present an O(mU) time...
Reactive Local Search for the Maximum Clique Problem
Reactive Local Search for the Maximum Clique Problem
2001,
A new Reactive Local Search ( LS ) algorithm is proposed for the solution of the...
Steiner Minimal Trees with One Polygonal Obstacle
Steiner Minimal Trees with One Polygonal Obstacle
2001,
In this paper we study the Steiner minimal tree T problem for a point set Z with...
On Nonlinear Parametric Search
On Nonlinear Parametric Search
2001,
An alternative viewpoint for parametric search is presented, which achieves a bound...
Optimal Edge Ranking of Trees in Linear Time
Optimal Edge Ranking of Trees in Linear Time
2001,
Given a tree, finding an optimal node ranking and finding an optimal edge ranking are...
A Generalization of a Lower Bound Technique due to Fredman and Saks
A Generalization of a Lower Bound Technique due to Fredman and Saks
2001,
In a seminal paper of 1989, Fredman and Saks proved lower bounds for some important...
Circular Separability of Polygons
Circular Separability of Polygons
2001,
Two planar sets are circularly separable if there exists a circle enclosing one of the...
Efficient Construction of Minimum Makespan Schedules for Tasks with a Fixed Number of Distinct Execution Times
Efficient Construction of Minimum Makespan Schedules for Tasks with a Fixed Number of Distinct Execution Times
2001,
This paper addresses scheduling problems for tasks with release and execution times....
Optimal Search and One‐Way Trading Online Algorithms
Optimal Search and One‐Way Trading Online Algorithms
2001,
This paper is concerned with the time series search and one‐way trading...
A One‐Step Crust and Skeleton Extraction Algorithm
A One‐Step Crust and Skeleton Extraction Algorithm
2001,
We wish to extract the topology from scanned maps. In previous work [GNY] this was...
Efficient Regular Data Structures and Algorithms for Dilation, Location, and Proximity Problems
Efficient Regular Data Structures and Algorithms for Dilation, Location, and Proximity Problems
2001,
In this paper we investigate data structures obtained by a recursive partitioning of...
Constraint‐Based Processing of Multiway Spatial Joins
Constraint‐Based Processing of Multiway Spatial Joins
2001,
A multiway spatial join combines information found in three or more spatial relations...
Robust Distance‐Based Clustering with Applications to Spatial Data Mining
Robust Distance‐Based Clustering with Applications to Spatial Data Mining
2001,
In this paper we present a method for clustering geo‐referenced data suitable...
Structural Lines, TINs, and DEMs
Structural Lines, TINs, and DEMs
2001,
The standard method of building compact triangulated surface approximations to terrain...
Papers per page: