Journal: Algorithmica

Found 758 papers in total
An Approximation Algorithm for Binary Searching in Trees
An Approximation Algorithm for Binary Searching in Trees
2011,
We consider the problem of computing efficient strategies for searching in trees. As a...
All‐Pairs Bottleneck Paths in Vertex Weighted Graphs
All‐Pairs Bottleneck Paths in Vertex Weighted Graphs
2011,
Let G =( V , E , w ) be a directed graph, where w : V →ℝ is a weight...
Time‐Dependent SHARC‐Routing
Time‐Dependent SHARC‐Routing
2011,
In recent years, many speed‐up techniques for Dijkstra’s algorithm have...
Deterministic Sampling Algorithms for Network Design
Deterministic Sampling Algorithms for Network Design
2011,
For several NP‐hard network design problems, the best known approximation...
Coupled Path Planning, Region Optimization, and Applications in Intensity‐modulated Radiation Therapy
Coupled Path Planning, Region Optimization, and Applications in Intensity‐modulated Radiation Therapy
2011,
In this paper, we consider an optimization problem in discrete geometry, called...
Better and Simpler Approximation Algorithms for the Stable Marriage Problem
Better and Simpler Approximation Algorithms for the Stable Marriage Problem
2011,
We first consider the problem of finding a maximum size stable matching if incomplete...
An Integer Programming Algorithm for Routing Optimization in IP Networks
An Integer Programming Algorithm for Routing Optimization in IP Networks
2011,
Most data networks nowadays use shortest path protocols to route the traffic. Given...
Approximate Range Searching in External Memory
Approximate Range Searching in External Memory
2011,
In this paper, we present two linear‐size external memory data structures for...
The Stackelberg Minimum Spanning Tree Game
The Stackelberg Minimum Spanning Tree Game
2011,
We consider a one‐round two‐player network pricing game, the Stackelberg...
Augmenting the Rigidity of a Graph in R2
Augmenting the Rigidity of a Graph in R2
2011,
Given a Laman graph G , i.e. a minimally rigid graph in R 2 , we provide a Θ ( n...
Exact Algorithms for L(2,1)‐Labeling of Graphs
Exact Algorithms for L(2,1)‐Labeling of Graphs
2011,
The notion of distance constrained graph labelings, motivated by the Frequency...
Improved Algorithms for Maximum Agreement and Compatible Supertrees
Improved Algorithms for Maximum Agreement and Compatible Supertrees
2011,
Consider a set of labels L and a set of unordered trees 𝒯={𝒯 (1)...
35/44‐approximation for Asymmetric Maximum TSP with Triangle Inequality
35/44‐approximation for Asymmetric Maximum TSP with Triangle Inequality
2011,
We describe a new approximation algorithm for the asymmetric maximum traveling...
Finding Total Unimodularity in Optimization Problems Solved by Linear Programs
Finding Total Unimodularity in Optimization Problems Solved by Linear Programs
2011,
A popular approach in combinatorial optimization is to model problems as integer...
Linear‐Time Construction of Two‐Dimensional Suffix Trees
Linear‐Time Construction of Two‐Dimensional Suffix Trees
2011,
The two-dimensional suffix tree of a matrix A is a compacted tree that represents all...
Precision, Local Search and Unimodal Functions
Precision, Local Search and Unimodal Functions
2011,
We investigate the effects of precision on the efficiency of various local search...
Computing Minimum Cuts by Randomized Search Heuristics
Computing Minimum Cuts by Randomized Search Heuristics
2011,
We study the minimum s ‐ t ‐cut problem in graphs with costs on the...
Hybridizing Evolutionary Algorithms with Variable‐Depth Search to Overcome Local Optima
Hybridizing Evolutionary Algorithms with Variable‐Depth Search to Overcome Local Optima
2011,
Hybridizing evolutionary algorithms with local search has become a popular trend in...
Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation
Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation
2011,
Drift analysis is a powerful tool used to bound the optimization time of evolutionary...
Lower Bounds for Comparison Based Evolution Strategies Using VC‐dimension and Sign Patterns
Lower Bounds for Comparison Based Evolution Strategies Using VC‐dimension and Sign Patterns
2011,
We derive lower bounds on the convergence rate of comparison based or selection based...
Combining Markov‐Chain Analysis and Drift Analysis
Combining Markov‐Chain Analysis and Drift Analysis
2011,
In their seminal article Droste, Jansen, and Wegener (2002) consider a basic...
Log‐Linear Convergence and Divergence of the Scale‐Invariant (1+1)‐ES in Noisy Environments
Log‐Linear Convergence and Divergence of the Scale‐Invariant (1+1)‐ES in Noisy Environments
2011,
Noise is present in many real‐world continuous optimization problems....
Random 2 XORSAT Phase Transition
Random 2 XORSAT Phase Transition
2011,
We consider the 2‐XOR satisfiability problem, in which each instance is a...
On Dissemination Thresholds in Regular and Irregular Graph Classes
On Dissemination Thresholds in Regular and Irregular Graph Classes
2011,
We investigate the natural situation of the dissemination of information on various...
Papers per page: