Search ACM DL

Search Issue

enter search term and/or author name

**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 *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...