Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 14 Issue 1, January 2018

Cache-Oblivious Buffer Heap and Cache-Efficient Computation of Shortest Paths in Graphs
Rezaul A. Chowdhury, Vijaya Ramachandran
Article No.: 1
DOI: 10.1145/3147172

We present the buffer heap, a cache-oblivious priority queue that supports Delete-Min, Delete, and a hybrid Insert/Decrease-Key operation in O(1/B log2 N/M) amortized block...

The Parametric Closure Problem
David Eppstein
Article No.: 2
DOI: 10.1145/3147212

We define the parametric closure problem, in which the input is a partially ordered set whose elements have linearly varying weights and the goal is to compute the sequence of minimum-weight downsets of the partial order as the weights...

Independence and Efficient Domination on P6-free Graphs
Daniel Lokshtanov, Marcin Pilipczuk, Erik Jan Van Leeuwen
Article No.: 3
DOI: 10.1145/3147214

In the Maximum Weight Independent Set problem, the input is a graph G, every vertex has a non-negative integer weight, and the task is to find a set S of pairwise nonadjacent vertices,...

Binary Adder Circuits of Asymptotically Minimum Depth, Linear Size, and Fan-Out Two
Stephan Held, Sophie Theresa Spirkl
Article No.: 4
DOI: 10.1145/3147215

We consider the problem of constructing fast and small binary adder circuits. Among widely used adders, the Kogge-Stone adder is often considered the fastest, because it computes the carry bits for two n-bit numbers (where n is a...

Primal Dual Gives Almost Optimal Energy-Efficient Online Algorithms
Nikhil R. Devanur, Zhiyi Huang
Article No.: 5
DOI: 10.1145/3155297

We consider the problem of online scheduling of jobs on unrelated machines with dynamic speed scaling to minimize the sum of energy and weighted flow-time. We give an algorithm with an almost optimal competitive ratio for arbitrary power...

Kernels for (Connected) Dominating Set on Graphs with Excluded Topological Minors
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos
Article No.: 6
DOI: 10.1145/3155298

We give the first linear kernels for the Dominating Set and Connected Dominating Set problems on graphs excluding a fixed graph H as a topological minor. In other words, we prove the...

Linear Time Parameterized Algorithms for Subset Feedback Vertex Set
Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh
Article No.: 7
DOI: 10.1145/3155299

In the Subset Feedback Vertex Set (Subset FVS) problem, the input is a graph G on n vertices and m edges, a subset of vertices T, referred to as terminals, and an...

Scaling Algorithms for Weighted Matching in General Graphs
Ran Duan, Seth Pettie, Hsin-Hao Su
Article No.: 8
DOI: 10.1145/3155301

We present a new scaling algorithm for maximum (or minimum) weight perfect matching on general, edge weighted graphs. Our algorithm runs in O(m&sqrt;nlog(nN)) time, O(m&sqrt; n) per scale, which...

Reducing Curse of Dimensionality: Improved PTAS for TSP (with Neighborhoods) in Doubling Metrics
T.-H. Hubert Chan, Shaofeng H.-C. Jiang
Article No.: 9
DOI: 10.1145/3158232

We consider the Traveling Salesman Problem with Neighborhoods (TSPN) in doubling metrics. The goal is to find the shortest tour that visits each of a given collection of subsets (regions or neighborhoods) in the underlying metric space.


Fault-Tolerant Approximate BFS Structures
Merav Parter, David Peleg
Article No.: 10
DOI: 10.1145/3022730

A fault-tolerant structure for a network is required to continue functioning following the failure of some of the network’s edges or vertices. This article addresses the problem of designing a fault-tolerant (α ,...