Journal: Algorithmica

Found 758 papers in total
Right‐Triangulated Irregular Networks
Right‐Triangulated Irregular Networks
2001,
We describe a hierarchical data structure for representing a digital terrain (height...
An Iterative Displacement Method for Conflict Resolution in Map Generalization
An Iterative Displacement Method for Conflict Resolution in Map Generalization
2001,
Cartographic generalization involves a trade‐off between information content,...
Automated Displacement for Large Numbers of Discrete Map Objects
Automated Displacement for Large Numbers of Discrete Map Objects
2001,
Effective displacement is achieved by sharing small movements among a group of objects...
Contextual Building Typification in Automated Map Generalization
Contextual Building Typification in Automated Map Generalization
2001,
Cartographic generalization aims to represent geographical information on a map whose...
Three Rules Suffice for Good Label Placement
Three Rules Suffice for Good Label Placement
2001,
The general label‐placement problem consists in labeling a set of features...
On Rooted Node‐Connectivity Problems
On Rooted Node‐Connectivity Problems
2001,
Let G be a graph which is k ‐outconnected from a specified root node r , that...
Random Sampling of Euler Tours
Random Sampling of Euler Tours
2001,
We define a Markov chain on the set of Euler tours of a given Eulerian graph based on...
Polynomial Time Approximation Schemes for Some Dense Instances of NP‐Hard Optimization Problems
Polynomial Time Approximation Schemes for Some Dense Instances of NP‐Hard Optimization Problems
2001,
We survey recent results on the existence of polynomial time approximation schemes for...
Best Possible Approximation Algorithm for MAX SAT with Cardinality Constraint
Best Possible Approximation Algorithm for MAX SAT with Cardinality Constraint
2001,
We consider the MAX SAT problem with the additional constraint that at most P...
An Approximation Algorithm for Circular Arc Colouring
An Approximation Algorithm for Circular Arc Colouring
2001,
We consider the problem of colouring a family of n arcs of a circle. This...
Sample Spaces with Small Bias on Neighborhoods and Error‐Correcting Communication Protocols
Sample Spaces with Small Bias on Neighborhoods and Error‐Correcting Communication Protocols
2001,
We give a deterministic algorithm which, on input an integer n , collection \cal F of...
On the Hardness of Approximating Spanners
On the Hardness of Approximating Spanners
2001,
A k ‐spanner of a connected graph G=(V,E) is a subgraph G' consisting of all...
Approximation of Geometric Dispersion Problems
Approximation of Geometric Dispersion Problems
2001,
We consider problems of distributing a number of points within a polygonal region P ,...
Geometry Helps in Bottleneck Matching and Related Problems
Geometry Helps in Bottleneck Matching and Related Problems
2001,
Let A and B be two sets of n objects in ℝ d , and let Match be a...
On‐Line Competitive Algorithms for Call Admission in Optical Networks
On‐Line Competitive Algorithms for Call Admission in Optical Networks
2001,
We study the on‐line call admission problem in optical networks. We present a...
Permutation Routing on Reconfigurable Meshes
Permutation Routing on Reconfigurable Meshes
2001,
In this paper we present efficient algorithms for packet routing on the reconfigurable...
Approximation Algorithms for Degree‐Constrained Minimum‐Cost Network‐Design Problems
Approximation Algorithms for Degree‐Constrained Minimum‐Cost Network‐Design Problems
2001,
We study network‐design problems with two different design objectives: the...
Inapproximability Results for Guarding Polygons and Terrains
Inapproximability Results for Guarding Polygons and Terrains
2001,
Past research on art gallery problems has concentrated almost exclusively on bounds on...
Lopsided Trees, I: Analyses
Lopsided Trees, I: Analyses
2001,
Lopsided trees are rooted, ordered trees in which the length of an edge from a node to...
The Asymptotic Number of Leftist Trees
The Asymptotic Number of Leftist Trees
2001,
It is shown that the number of leftist trees of size n in a simply generated family of...
Average Profile of the Lempel‐Ziv Parsing Scheme for a Markovian Source
Average Profile of the Lempel‐Ziv Parsing Scheme for a Markovian Source
2001,
For a Markovian source, we analyze the Lempel–Ziv parsing scheme that partitions...
Analytic Variations on the Airy Distribution
Analytic Variations on the Airy Distribution
2001,
The Airy distribution (of the ‘area’ type) occurs as a limit distribution...
Efficient Reorganization of Binary Search Trees
Efficient Reorganization of Binary Search Trees
2001,
We consider the problem of maintaining a binary search tree ({ bst }) that minimizes...
A Limit Law for Outputs in Random Recursive Circuits
A Limit Law for Outputs in Random Recursive Circuits
2001,
We study the structure of uniform random binary recursive circuits. We show that a...
Papers per page: