Journal: Algorithmica

Found 758 papers in total
Pinwheel Scheduling: Achievable Densities
Pinwheel Scheduling: Achievable Densities
2002,
A pinwheel schedule for a vector v= (v 1 , v 2 , …, v n ) of positive integers...
Splitting a Delaunay Triangulation in Linear Time
Splitting a Delaunay Triangulation in Linear Time
2002,
Computing the Delaunay triangulation of n points requires usually a minimum of...
The Analysis of Evolutionary Algorithms–A Proof That Crossover Really Can Help
The Analysis of Evolutionary Algorithms–A Proof That Crossover Really Can Help
2002,
Evolutionary algorithms are randomized search heuristics that were invented in the...
Testing and Spot‐Checking of Data Streams
Testing and Spot‐Checking of Data Streams
2002,
We consider the tasks of testing and spot‐checking for data streams . These...
Realistic Input Models for Geometric Algorithms
Realistic Input Models for Geometric Algorithms
2002,
The traditional worst‐case analysis often fails to predict the actual behavior...
Erratum: An Approximation Algorithm for Minimum‐Cost Vertex‐Connectivity Problems
Erratum: An Approximation Algorithm for Minimum‐Cost Vertex‐Connectivity Problems
2002,
There is an error in our paper “An Approximation Algorithm for...
Near‐Linear Approximation Algorithms for Geometric Hitting Sets
Near‐Linear Approximation Algorithms for Geometric Hitting Sets
2012,
Given a range space ( X , ℛ ) , where ℛ ⊂ 2 X , the hitting set...
Graph Decomposition for Memoryless Periodic Exploration
Graph Decomposition for Memoryless Periodic Exploration
2012,
We consider a general framework in which a memoryless robot periodically explores all...
Almost Exact Matchings
Almost Exact Matchings
2012,
In the exact matching problem we are given a graph G , some of whose edges are colored...
Contribution Games in Networks
Contribution Games in Networks
2012,
We consider network contribution games , where each agent in a network has a budget of...
On the Hitting Times of Quantum Versus Random Walks
On the Hitting Times of Quantum Versus Random Walks
2012,
The hitting time of a classical random walk (Markov chain) is the time required to...
Reducing Tile Complexity for the Self‐assembly of Scaled Shapes Through Temperature Programming
Reducing Tile Complexity for the Self‐assembly of Scaled Shapes Through Temperature Programming
2012,
This paper concerns the self‐assembly of scaled‐up versions of arbitrary...
Maximum Series‐Parallel Subgraph
Maximum Series‐Parallel Subgraph
2012,
Consider the NP‐hard problem of, given a simple graph G , to find a...
A Distributed Algorithm for Computing the Node Search Number in Trees
A Distributed Algorithm for Computing the Node Search Number in Trees
2012,
We present a distributed algorithm to compute the node search number in trees. This...
A Primal‐Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties
A Primal‐Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties
2012,
We consider the facility location problem with submodular penalties (FLPSP),...
Succinct and I/O Efficient Data Structures for Traversal in Trees
Succinct and I/O Efficient Data Structures for Traversal in Trees
2012,
We present two results for path traversal in trees, where the traversal is performed...
Faster Algorithms for All‐Pairs Small Stretch Distances in Weighted Graphs
Faster Algorithms for All‐Pairs Small Stretch Distances in Weighted Graphs
2012,
Let G =( V , E ) be a weighted undirected graph, with non‐negative edge...
On Equilibria for ADM Minimization Games
On Equilibria for ADM Minimization Games
2012,
In the ADM minimization problem the input is a set of arcs along a directed ring. The...
Minimize the Maximum Duty in Multi‐interface Networks
Minimize the Maximum Duty in Multi‐interface Networks
2012,
We consider devices equipped with multiple wired or wireless interfaces. By switching...
A Competitive Analysis for Balanced Transactional Memory Workloads
A Competitive Analysis for Balanced Transactional Memory Workloads
2012,
We consider transactional memory contention management in the context of balanced...
An Exact Exponential Time Algorithm for Power Dominating Set
An Exact Exponential Time Algorithm for Power Dominating Set
2012,
The Power Dominating Set problem is an extension of the well‐known domination...
Improved Approximation Algorithms for Data Migration
Improved Approximation Algorithms for Data Migration
2012,
Our work is motivated by the need to manage data items on a collection of storage...
Interval Partitions and Polynomial Factorization
Interval Partitions and Polynomial Factorization
2012,
The fastest algorithms for factoring a univariate polynomial f of degree n over a...
Approximating Node‐Connectivity Augmentation Problems
Approximating Node‐Connectivity Augmentation Problems
2012,
We consider the (undirected) Node Connectivity Augmentation ( NCA ) problem: given a...
Papers per page: