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
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
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
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
Given a graph G and an integer k, the
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
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...
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
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
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...
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
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
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...