enter search term and/or author name
Cache-Oblivious Buffer Heap and Cache-Efficient Computation of Shortest Paths in Graphs
Rezaul A. Chowdhury, Vijaya Ramachandran
Article No.: 1
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...
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
In the M
Binary Adder Circuits of Asymptotically Minimum Depth, Linear Size, and Fan-Out Two
Stephan Held, Sophie Theresa Spirkl
Article No.: 4
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
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
We give the first linear kernels for the D
Linear Time Parameterized Algorithms for S
Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh
Article No.: 7
In the S
Scaling Algorithms for Weighted Matching in General Graphs
Ran Duan, Seth Pettie, Hsin-Hao Su
Article No.: 8
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
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.
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 (α ,...