Journal: Algorithmica

Found 758 papers in total
An Efficient Algorithm for Haplotype Inference on Pedigrees with a Small Number of Recombinants
An Efficient Algorithm for Haplotype Inference on Pedigrees with a Small Number of Recombinants
2012,
Combinatorial (or rule‐based) methods for inferring haplotypes from genotypes...
On the Complexity of Optimal Hotlink Assignment
On the Complexity of Optimal Hotlink Assignment
2012,
The concept of hotlink assignment aims at reducing the navigation effort for users of...
Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pebbles
Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pebbles
2012,
We prove that, for the black hole search problem in networks of arbitrary but known...
A Constant‐Approximate Feasibility Test for Multiprocessor Real‐Time Scheduling
A Constant‐Approximate Feasibility Test for Multiprocessor Real‐Time Scheduling
2012,
We devise an approximate feasibility test for multiprocessor real‐time...
A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs
A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs
2012,
We consider the problem of partitioning the set of vertices of a given unit disk graph...
Fully Dynamic Geometric Spanners
Fully Dynamic Geometric Spanners
2012,
In this paper we present an algorithm for maintaining a spanner over a dynamic set of...
Continuous Monitoring of Distributed Data Streams over a Time‐Based Sliding Window
Continuous Monitoring of Distributed Data Streams over a Time‐Based Sliding Window
2012,
In this paper we extend the study of algorithms for monitoring distributed data...
Approximating Optimal Binary Decision Trees
Approximating Optimal Binary Decision Trees
2012,
We give a (ln n +1)‐approximation for the decision tree (DT) problem. An...
A Linear‐Time Algorithm for Star‐Shaped Drawings of Planar Graphs with the Minimum Number of Concave Corners
A Linear‐Time Algorithm for Star‐Shaped Drawings of Planar Graphs with the Minimum Number of Concave Corners
2012,
A star‐shaped drawing of a graph is a straight‐line drawing such that...
Schnyder Decompositions for Regular Plane Graphs and Application to Drawing
Schnyder Decompositions for Regular Plane Graphs and Application to Drawing
2012,
Schnyder woods are decompositions of simple triangulations into three...
Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems
Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems
2012,
Constant‐factor, polynomial‐time approximation algorithms are presented...
Efficient Parallel Algorithms for Planar st‐Graphs
Efficient Parallel Algorithms for Planar st‐Graphs
2003,
Planar st ‐graphs find applications in a number of areas. In this paper we...
An Approximation Algorithm for a Large‐Scale Facility Location Problem
An Approximation Algorithm for a Large‐Scale Facility Location Problem
2003,
We developed a new practical optimization method that gives approximate solutions for...
Finding a Region with the Minimum Total L 1 Distance from Prescribed Terminals
Finding a Region with the Minimum Total L 1 Distance from Prescribed Terminals
2003,
Given k terminals and n axis‐parallel rectangular obstacles on the plane, our...
A Randomized Linear‐Work EREW PRAM Algorithm to Find a Minimum Spanning Forest
A Randomized Linear‐Work EREW PRAM Algorithm to Find a Minimum Spanning Forest
2003,
We present a randomized EREW PRAM algorithm to find a minimum spanning forest in a...
A Characterization of Planar Graphs by Pseudo‐Line Arrangements
A Characterization of Planar Graphs by Pseudo‐Line Arrangements
2003,
Let Γ be an arrangement of pseudo‐lines, i.e., a collection of unbounded...
Dynamic TCP Acknowledgment and Other Stories about e/(e ‐ 1)
Dynamic TCP Acknowledgment and Other Stories about e/(e ‐ 1)
2003,
We present the first optimal randomized online algorithms for the TCP acknowledgment...
Competitive On‐Line Switching Policies
Competitive On‐Line Switching Policies
2003,
Consider the following problem. A switch connecting n input channels to a single...
Static Optimality and Dynamic Search‐Optimality in Lists and Trees
Static Optimality and Dynamic Search‐Optimality in Lists and Trees
2003,
Adaptive data structures form a central topic of on‐line algorithms research....
New Bounds for Multidimensional Packing
New Bounds for Multidimensional Packing
2003,
New upper and lower bounds are presented for a multidimensional generalization of bin...
Temporary Tasks Assignment Resolved
Temporary Tasks Assignment Resolved
2003,
Among all basic on‐line load balancing problems, the only unresolved problem...
Multicast Pull Scheduling: When Fairness Is Fine
Multicast Pull Scheduling: When Fairness Is Fine
2003,
We investigate server scheduling policies to minimize average user perceived latency...
The Buffer Tree: A Technique for Designing Batched External Data Structures
The Buffer Tree: A Technique for Designing Batched External Data Structures
2003,
We present a technique for designing external memory data structures that support...
Computing the Maximum Degree of Minors in Matrix Pencils via Combinatorial Relaxation
Computing the Maximum Degree of Minors in Matrix Pencils via Combinatorial Relaxation
2003,
This paper presents a new algorithm for computing the maximum degree δk (A) of a...
Papers per page: