Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 11 Issue 4, June 2015

On the Performance of Smith’s Rule in Single-Machine Scheduling with Nonlinear Cost
Wiebke Höhn, Tobias Jacobs
Article No.: 25
DOI: 10.1145/2629652

We consider a single-machine scheduling problem. Given some continuous, nondecreasing cost function, we aim to compute a schedule minimizing the weighted total cost, where the cost of each job is determined by the cost function value at its...

Computing Shortest Paths among Curved Obstacles in the Plane
Danny Z. Chen, Haitao Wang
Article No.: 26
DOI: 10.1145/2660771

A fundamental problem in computational geometry is to compute an obstacle-avoiding Euclidean shortest path between two points in the plane. The case of this problem on polygonal obstacles is well studied. In this article, we consider the problem...

Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation
Dániel Marx, László A. Végh
Article No.: 27
DOI: 10.1145/2700210

We consider connectivity-augmentation problems in a setting where each potential new edge has a non-negative cost associated with it, and the task is to achieve a certain connectivity target with at most p new edges of minimum total cost....

Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
Rajesh Chitnis, Marek Cygan, Mohammataghi Hajiaghayi, Dániel Marx
Article No.: 28
DOI: 10.1145/2700209

Given a graph G and an integer k, the Feedback Vertex Set (FVS) problem asks if there is a vertex set T of size at most k that hits all cycles in the graph. The first fixed-parameter algorithm for FVS in...

The Discrete and Semicontinuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection
Rinat Ben Avraham, Omrit Filtser, Haim Kaplan, Matthew J. Katz, Micha Sharir
Article No.: 29
DOI: 10.1145/2700222

The Fréchet distance is a well-studied similarity measure between curves. The discrete Fréchet distance is an analogous similarity measure, defined for two sequences of m and n points, where the points are...

Rank-Balanced Trees
Bernhard Haeupler, Siddhartha Sen, Robert E. Tarjan
Article No.: 30
DOI: 10.1145/2689412

Since the invention of AVL trees in 1962, many kinds of binary search trees have been proposed. Notable are red-black trees, in which bottom-up rebalancing after an insertion or deletion takes O(1) amortized time and O(1) rotations worst-case. But...

Optimal Lower and Upper Bounds for Representing Sequences
Djamal Belazzougui, Gonzalo Navarro
Article No.: 31
DOI: 10.1145/2629339

Sequence representations supporting the queries access, select, and rank are at the core of many data structures. There is a considerable gap between the various upper bounds and the few lower bounds known for such...

Testing Planarity of Partially Embedded Graphs
Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Vít Jelínek, Jan Kratochvíl, Maurizio Patrignani, Ignaz Rutter
Article No.: 32
DOI: 10.1145/2629341

We study the following problem: given a planar graph G and a planar drawing (embedding) of a subgraph of G, can such a drawing be extended to a planar drawing of the entire graph G? This problem fits the paradigm of...

Mapping Simple Polygons: The Power of Telling Convex from Reflex
Jérémie Chalopin, Shantanu Das, Yann Disser, Matúš Mihalák, Peter Widmayer
Article No.: 33
DOI: 10.1145/2700223

We consider the exploration of a simple polygon P by a robot that moves from vertex to vertex along edges of the visibility graph of P. The visibility graph has a vertex for every vertex of P and an edge between two vertices...

A Bounded Budget Network Creation Game
Shayan Ehsani, Saber Shokat Fadaee, Mohammadamin Fazli, Abbas Mehrabian, Sina Sadeghian Sadeghabad, Mohammadali Safari, Morteza Saghafian
Article No.: 34
DOI: 10.1145/2701615

We introduce a network creation game in which each player (vertex) has a fixed budget to establish links to other players. In this model, each link has a unit price, and each agent tries to minimize its cost, which is either its eccentricity or...

An Improved Competitive Algorithm for Reordering Buffer Management
Noa Avigdor-Elgrabli, Yuval Rabani
Article No.: 35
DOI: 10.1145/2663347

We design and analyze an online reordering buffer management algorithm with improved O(log k/log log k) competitive ratio for nonuniform costs, where k is the buffer size. This improves on the best...