Journal: Algorithmica

Found 758 papers in total
Escaping a Grid by Edge‐Disjoint Paths
Escaping a Grid by Edge‐Disjoint Paths
2003,
We present a technique for designing external memory data structures that support...
Polynomial Time Algorithms for 2‐Edge‐Connectivity Augmentation Problems
Polynomial Time Algorithms for 2‐Edge‐Connectivity Augmentation Problems
2003,
Given a 2‐edge‐connected, real weighted graph G with n vertices and m...
Computing the Treewidth and the Minimum Fill‐In with the Modular Decomposition
Computing the Treewidth and the Minimum Fill‐In with the Modular Decomposition
2003,
Using the notion of modular decomposition we extend the class of graphs on which both...
Fixed‐Parameter Algorithms for CLOSEST STRING and Related Problems
Fixed‐Parameter Algorithms for CLOSEST STRING and Related Problems
2003,
CLOSEST STRING is one of the core problems in the field of consensus word analysis...
Linear Bidirectional On‐Line Construction of Affix Trees
Linear Bidirectional On‐Line Construction of Affix Trees
2003,
Affix trees are a generalization of suffix trees that are based on the inherent...
An Edit Distance between Quotiented Trees
An Edit Distance between Quotiented Trees
2003,
In this paper we propose a dynamic programming algorithm to compare two quotiented...
The Solution of Linear Probabilistic Recurrence Relations
The Solution of Linear Probabilistic Recurrence Relations
2003,
Linear probabilistic divide‐and‐conquer recurrence relations arise when...
Maintenance of a Piercing Set for Intervals with Applications
Maintenance of a Piercing Set for Intervals with Applications
2003,
We show how to maintain efficiently a minimum piercing set for a set S of intervals on...
A Heuristic for Dijkstra's Algorithm with Many Targets and Its Use in Weighted Matching Algorithms
A Heuristic for Dijkstra's Algorithm with Many Targets and Its Use in Weighted Matching Algorithms
2003,
We consider the single‐source many‐targets shortest‐path (SSMTSP)...
Efficient External Memory Algorithms by Simulating Coarse‐Grained Parallel Algorithms
Efficient External Memory Algorithms by Simulating Coarse‐Grained Parallel Algorithms
2003,
External memory (EM) algorithms are designed for large‐scale computational...
An O(n 1.5 ) Deterministic Gossiping Algorithm for Radio Networks
An O(n 1.5 ) Deterministic Gossiping Algorithm for Radio Networks
2003,
We consider the problem of distributed gossiping in radio networks of unknown...
Drawing Trees Symmetrically in Three Dimensions
Drawing Trees Symmetrically in Three Dimensions
2003,
Symmetric graph drawing enables a clear understanding of the structure of the graph....
Time‐Constrained Scheduling of Weighted Packets on Trees and Meshes
Time‐Constrained Scheduling of Weighted Packets on Trees and Meshes
2003,
The time‐constrained packet routing problem is to schedule a set of packets to...
A New Approximation Algorithm for Finding Heavy Planar Subgraphs
A New Approximation Algorithm for Finding Heavy Planar Subgraphs
2003,
We provide the first nontrivial approximation algorithm for MAXIMUM WEIGHT PLANAR...
The Minimum Range Assignment Problem on Linear Radio Networks
The Minimum Range Assignment Problem on Linear Radio Networks
2003,
Given a set S of radio stations located on a line and an integer h ≥ 1 , the MIN...
TSP Heuristics: Domination Analysis and Complexity
TSP Heuristics: Domination Analysis and Complexity
2003,
We show that the 2‐Opt and 3‐Opt heuristics for the traveling salesman...
Dynamic Programming on the Word RAM
Dynamic Programming on the Word RAM
2003,
Dynamic programming is one of the fundamental techniques for solving optimization...
The Data Broadcast Problem with Non‐Uniform Transmission Times
The Data Broadcast Problem with Non‐Uniform Transmission Times
2003,
The Data Broadcast Problem consists of finding an infinite schedule to broadcast a...
On‐Line Edge‐Coloring with a Fixed Number of Colors
On‐Line Edge‐Coloring with a Fixed Number of Colors
2003,
We investigate a variant of on‐line edge‐coloring in which there is a...
Optimal Reconstruction of Graphs under the Additive Model
Optimal Reconstruction of Graphs under the Additive Model
2000,
We study the problem of reconstructing unknown graphs under the additive combinatorial...
Fault‐Tolerant Real‐Time Scheduling
Fault‐Tolerant Real‐Time Scheduling
2000,
We use competitive analysis to study how best to use redundancy to achieve...
Approximating Satisfiable Satisfiability Problems
Approximating Satisfiable Satisfiability Problems
2000,
We study the approximability of the Maximum Satisfiability Problem (MAX SAT) and of...
Experimental Analysis of Heuristic Algorithms for the Dominating Set Problem
Experimental Analysis of Heuristic Algorithms for the Dominating Set Problem
2002,
We say a vertex v in a graph G covers a vertex w if v=w or if v and w are adjacent. A...
An Experimental Study of Compression Methods for Dynamic Tries
An Experimental Study of Compression Methods for Dynamic Tries
2002,
We study an order‐preserving general purpose data structure for binary data,...
Papers per page: