Journal: Algorithmica

Found 758 papers in total
Exact Largest and Smallest Size of Components
Exact Largest and Smallest Size of Components
2001,
Golomb and Gaal [15] study the number of permutations on n objects with largest cycle...
A q ‐Analogue of the Path Length of Binary Search Trees
A q ‐Analogue of the Path Length of Binary Search Trees
2001,
A reformulation of the path length of binary search trees is given in terms of...
Stochastic Analysis of Shell Sort
Stochastic Analysis of Shell Sort
2001,
We analyze the Shell Sort algorithm under the usual random permutation model. Using...
Uniquely Restricted Matchings
Uniquely Restricted Matchings
2001,
A matching in a graph is a set of edges no two of which share a common vertex. In this...
Bounded Space On‐Line Bin Packing: Best Is Better than First
Bounded Space On‐Line Bin Packing: Best Is Better than First
2001,
We present a sequence of new linear‐time, bounded‐space, on‐line...
An Efficient Output‐Size Sensitive Parallel Algorithm for Hidden‐Surface Removal for Terrains
An Efficient Output‐Size Sensitive Parallel Algorithm for Hidden‐Surface Removal for Terrains
2001,
We describe an efficient parallel algorithm for hidden‐surface removal for...
All‐to‐All Optical Routing in Chordal Rings of Degree 4
All‐to‐All Optical Routing in Chordal Rings of Degree 4
2001,
We consider the problem of routing in networks employing all‐optical routing...
Searching for Mobile Intruders in a Polygonal Region by a Group of Mobile Searchers
Searching for Mobile Intruders in a Polygonal Region by a Group of Mobile Searchers
2001,
The problem of searching for mobile intruders in a polygonal region by mobile...
Exact Algorithms for Linear Programming over Algebraic Extensions
Exact Algorithms for Linear Programming over Algebraic Extensions
2001,
We study the computational complexity of linear programs with coefficients that are...
Grade of Service Steiner Minimum Trees in the Euclidean Plane
Grade of Service Steiner Minimum Trees in the Euclidean Plane
2001,
Let P = {p 1 , p 2 , \ldots, p n } be a set of n {\lilsf terminal points} in the...
Relaxed Balance Using Standard Rotations
Relaxed Balance Using Standard Rotations
2001,
In search trees with relaxed balance, rebalancing transformations need not be...
Reconstructing a Minimum Spanning Tree after Deletion of Any Node
Reconstructing a Minimum Spanning Tree after Deletion of Any Node
2001,
Updating a minimum spanning tree (MST) is a basic problem for communication networks....
An Algorithm for Computing a Convex and Simple Path of Bounded Curvature in a Simple Polygon
An Algorithm for Computing a Convex and Simple Path of Bounded Curvature in a Simple Polygon
2002,
In this paper we study the collision-free path planning problem for a point robot,...
Further Thoughts on the Syntenic Distance between Genomes
Further Thoughts on the Syntenic Distance between Genomes
2002,
The syntenic distance between two multi-chromosomal genomes is the minimum number of...
Partitioning a Square into Rectangles: NP‐Completeness and Approximation Algorithms
Partitioning a Square into Rectangles: NP‐Completeness and Approximation Algorithms
2002,
In this paper we deal with two geometric problems arising from heterogeneous parallel...
Max‐ and Min‐Neighborhood Monopolies
Max‐ and Min‐Neighborhood Monopolies
2002,
Given a graph G=(V,E) and a set of vertices M ⊆ V , a vertex v ∈ V is said...
Budget Management with Applications
Budget Management with Applications
2002,
Given a directed acyclic graph with timing constraints, the budget management problem...
Fair versus Unrestricted Bin Packing
Fair versus Unrestricted Bin Packing
2002,
We consider the on‐line Dual Bin Packing problem where we have n unit size bins...
Communication–Processor Tradeoffs in a Limited Resources PRAM
Communication–Processor Tradeoffs in a Limited Resources PRAM
2002,
We consider a simple restriction of the PRAM model (called PPRAM), where the input is...
Approximation Algorithms for Access Network Design
Approximation Algorithms for Access Network Design
2002,
We consider the problem of designing a minimum cost access network to carry traffic...
Planar Graph Blocking for External Searching
Planar Graph Blocking for External Searching
2002,
We present a new scheme for storing a planar graph in external memory so that any...
The Complexity of Counting Eulerian Tours in 4‐regular Graphs
The Complexity of Counting Eulerian Tours in 4‐regular Graphs
2012,
We investigate the complexity of counting Eulerian tours (# ET ) and its...
Pairs of Complementary Unary Languages with ‘Balanced’ Nondeterministic Automata
Pairs of Complementary Unary Languages with ‘Balanced’ Nondeterministic Automata
2012,
For each sufficiently large n , there exists a unary regular language L such that both...
Gradual Sub‐lattice Reduction and a New Complexity for Factoring Polynomials
Gradual Sub‐lattice Reduction and a New Complexity for Factoring Polynomials
2012,
We present a lattice algorithm specifically designed for some classical applications...
Papers per page: