Journal: Algorithmica

Found 758 papers in total
Improved Competitive Performance Bounds for CIOQ Switches
Improved Competitive Performance Bounds for CIOQ Switches
2012,
Combined Input and Output Queued (CIOQ) architectures with a moderate fabric speedup S...
Approximation Algorithms and Hardness Results for Packing Element‐Disjoint Steiner Trees in Planar Graphs
Approximation Algorithms and Hardness Results for Packing Element‐Disjoint Steiner Trees in Planar Graphs
2012,
We study the problem of packing element‐disjoint Steiner trees in graphs. We...
External Memory Planar Point Location with Logarithmic Updates
External Memory Planar Point Location with Logarithmic Updates
2012,
Point location is an extremely well‐studied problem both in internal memory...
Layered Working‐Set Trees
Layered Working‐Set Trees
2012,
The working‐set bound [Sleator and Tarjan in J. ACM 32(3), 652–686, 1985]...
Bipartite Matching in the Semi‐streaming Model
Bipartite Matching in the Semi‐streaming Model
2012,
We present the first deterministic 1+ ϵ approximation algorithm for finding...
Average Case Analysis of Moore’s State Minimization Algorithm
Average Case Analysis of Moore’s State Minimization Algorithm
2012,
We prove that the average complexity of Moore’s state minimization algorithm is...
Polynomial Kernelizations for MIN F+Π 1 and MAX NP
Polynomial Kernelizations for MIN F+Π 1 and MAX NP
2012,
It has been observed in many places that constant‐factor approximable problems...
Minimum Manhattan Network Problem in Normed Planes with Polygonal Balls: A Factor 2.5 Approximation Algorithm
Minimum Manhattan Network Problem in Normed Planes with Polygonal Balls: A Factor 2.5 Approximation Algorithm
2012,
Let ℬ be a centrally symmetric convex polygon of ℝ 2 and ∥ p - q...
Online Randomized Multiprocessor Scheduling
Online Randomized Multiprocessor Scheduling
2000,
The use of randomization in online multiprocessor scheduling is studied. The problem...
Parallel Algorithms for Partitioning Sorted Sets and Related Problems
Parallel Algorithms for Partitioning Sorted Sets and Related Problems
2000,
We consider the following partition problem: Given a set S of n elements that is...
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...
Simple Algorithms for the On‐Line Multidimensional Dictionary and Related Problems
Simple Algorithms for the On‐Line Multidimensional Dictionary and Related Problems
2000,
The on‐line multidimensional dictionary problem consists of executing...
Fast Spatial Decomposition and Closest Pair Computation for Limited Precision Input
Fast Spatial Decomposition and Closest Pair Computation for Limited Precision Input
2000,
In this paper we show that if the input points to the geometric closest pair problem...
A Unified Approach to Conic Visibility
A Unified Approach to Conic Visibility
2000,
In this paper we present linear time algorithms for computing the shortest path tree...
Sorting by Short Block‐Moves
Sorting by Short Block‐Moves
2000,
Sorting permutations by operations such as reversals and block‐moves has...
Linear Size Binary Space Partitions for Uncluttered Scenes
Linear Size Binary Space Partitions for Uncluttered Scenes
2000,
We describe a new and simple method for constructing binary space partitions (BSPs) in...
On Space Efficient Two Dimensional Range Minimum Data Structures
On Space Efficient Two Dimensional Range Minimum Data Structures
2012,
The two dimensional range minimum query problem is to preprocess a static m by n...
Caching Is Hard–Even in the Fault Model
Caching Is Hard–Even in the Fault Model
2012,
We prove strong ℕℙ ‐completeness for the four variants of caching...
Feasibility Analysis of Sporadic Real‐Time Multiprocessor Task Systems
Feasibility Analysis of Sporadic Real‐Time Multiprocessor Task Systems
2012,
We give the first algorithm for testing the feasibility of a system of sporadic...
When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings
When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings
2012,
Consider a random graph model where each possible edge e is present independently with...
f‐Sensitivity Distance Oracles and Routing Schemes
f‐Sensitivity Distance Oracles and Routing Schemes
2012,
An f‐sensitivity distance oracle for a weighted undirected graph G ( V , E ) is...
Local Search Algorithms for the Red‐Blue Median Problem
Local Search Algorithms for the Red‐Blue Median Problem
2012,
In this paper, we consider the following red‐blue median problem which is a...
A Complete Characterization of Group‐Strategyproof Mechanisms of Cost‐Sharing
A Complete Characterization of Group‐Strategyproof Mechanisms of Cost‐Sharing
2012,
We study the problem of designing group‐strategyproof cost‐sharing...
The Power of Fair Pricing Mechanisms
The Power of Fair Pricing Mechanisms
2012,
We explore the revenue capabilities of truthful, monotone (‘fair’)...
Papers per page: