Journal: Algorithmica

Found 758 papers in total
Scheduling Independent Multiprocessor Tasks
Scheduling Independent Multiprocessor Tasks
2002,
We study the problem of scheduling a set of n independent multiprocessor tasks with...
One‐by‐One Cleaning for Practical Parallel List Ranking
One‐by‐One Cleaning for Practical Parallel List Ranking
2002,
It is hard to achieve good speed‐ups for parallel list ranking on...
Property Testing in Bounded Degree Graphs
Property Testing in Bounded Degree Graphs
2002,
We further develop the study of testing graph properties as initiated by Goldreich,...
Lower Bounds for Dynamic Data Structures on Algebraic RAMs
Lower Bounds for Dynamic Data Structures on Algebraic RAMs
2002,
In a seminal paper of 1989, Fredman and Saks proved lower bounds for some important...
Minimum Congestion Redundant Assignments to Tolerate Random Faults
Minimum Congestion Redundant Assignments to Tolerate Random Faults
2002,
We consider the problem of computing minimum congestion, fault‐tolerant,...
Caching Documents with Variable Sizes and Fetching Costs: An LP‐Based Approach
Caching Documents with Variable Sizes and Fetching Costs: An LP‐Based Approach
2002,
We give an integer programming formulation of the paging problem with varying sizes...
Routing Flow Through a Strongly Connected Graph
Routing Flow Through a Strongly Connected Graph
2002,
It is shown that, for every strongly connected network in which every edge has...
Quasi‐Upward Planarity
Quasi‐Upward Planarity
2002,
An upward planar drawing of a directed graph (digraph) is a planar drawing such that...
Improved Algorithms for Uniform Partitions of Points
Improved Algorithms for Uniform Partitions of Points
2002,
We consider the following one‐ and two‐dimensional bucketing problems:...
Linear‐Time Approximation Schemes for Scheduling Malleable Parallel Tasks
Linear‐Time Approximation Schemes for Scheduling Malleable Parallel Tasks
2002,
A malleable parallel task is one whose execution time is a function of the number of...
An Online Algorithm for the Dynamic Maximal Dense Tree Problem
An Online Algorithm for the Dynamic Maximal Dense Tree Problem
2002,
The Online Maximal Dense Tree problem is as follows: given a weighted directed graph...
Embedding Linkages on an Integer Lattice
Embedding Linkages on an Integer Lattice
2002,
This paper answers the following question: Given an “erector set” linkage,...
A Functional Approach to External Graph Algorithms
A Functional Approach to External Graph Algorithms
2002,
We present a new approach for designing external graph algorithms and use it to design...
Approximations for a Bottleneck Steiner Tree Problem
Approximations for a Bottleneck Steiner Tree Problem
2002,
In the design of wireless communication networks, due to a budget limit, suppose we...
Distributed and On‐Line Routing on Tori
Distributed and On‐Line Routing on Tori
2002,
In this paper we study the problem of assigning paths to packets on N imes N tori in...
A Generalization of AT‐Free Graphs and a Generic Algorithm for Solving Triangulation Problems
A Generalization of AT‐Free Graphs and a Generic Algorithm for Solving Triangulation Problems
2002,
A subset A of the vertices of a graph G is an asteroidal set if for each vertex a...
Fault Identification in System‐Level Diagnosis: a Logic‐Based Framework and an O(n2\sqrt{t}/{\log n}) Algorithm
Fault Identification in System‐Level Diagnosis: a Logic‐Based Framework and an O(n2\sqrt{t}/{\log n}) Algorithm
2002,
Much research has been devoted to system‐level diagnosis–SLD. Two issues...
Algorithmic Aspects of Acyclic Edge Colorings
Algorithmic Aspects of Acyclic Edge Colorings
2002,
A proper coloring of the edges of a graph G is called acyclic if there is no...
A Probabilistic Algorithm for k ‐SAT Based on Limited Local Search and Restart
A Probabilistic Algorithm for k ‐SAT Based on Limited Local Search and Restart
2002,
A simple probabilistic algorithm for solving the NP‐complete problem k...
Randomized Weighted Caching with Two Page Weights
Randomized Weighted Caching with Two Page Weights
2002,
We consider a special case of the weighted caching problem where the weight of every...
Efficiently Approximating Polygonal Paths in Three and Higher Dimensions
Efficiently Approximating Polygonal Paths in Three and Higher Dimensions
2002,
We present efficient algorithms for solving polygonal‐path approximation...
Delayed Binary Search, or Playing Twenty Questions with a Procrastinator
Delayed Binary Search, or Playing Twenty Questions with a Procrastinator
2002,
We study the classic binary search problem, with a delay between query and answer. For...
Multiprocessor Scheduling with Machine Allotment and Parallelism Constraints
Multiprocessor Scheduling with Machine Allotment and Parallelism Constraints
2002,
Modern computer systems distribute computation among several machines to speed up the...
A Near‐Linear Area Bound for Drawing Binary Trees
A Near‐Linear Area Bound for Drawing Binary Trees
2002,
We present several simple methods to construct planar, strictly upward, strongly...
Papers per page: