Search ACM DL

Search Issue

enter search term and/or author name

**An in-place sorting with O(nlog n) comparisons and O(n) moves**

Gianni Franceschini, Viliam Geffert

Pages: 515-537

DOI: 10.1145/1082036.1082037

We present the first in-place algorithm for sorting an array of size

**Asymmetric k-center is log^{*} n-hard to approximate**

Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, Joseph (Seffi) Naor

Pages: 538-551

DOI: 10.1145/1082036.1082038

In the ASYMMETRIC

**Indexing compressed text**

Paolo Ferragina, Giovanni Manzini

Pages: 552-581

DOI: 10.1145/1082036.1082039

We design two compressed data structures for the full-text indexing problem that support efficient substring searches using roughly the space required for storing the text in compressed form.Our first compressed data structure retrieves the...

**Source routing and scheduling in packet networks**

Matthew Andrews, Antonio Fernández, Ashish Goel, Lisa Zhang

Pages: 582-601

DOI: 10.1145/1082036.1082040

We study *routing* and *scheduling* in packet-switched networks. We assume an adversary that controls the injection time, source, and destination for each packet injected. A set of paths for these packets is *admissible* if no link in...

**Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs**

Haim Kaplan, Moshe Lewenstein, Nira Shafrir, Maxim Sviridenko

Pages: 602-626

DOI: 10.1145/1082036.1082041

A directed multigraph is said to be *d*-regular if the indegree and outdegree of every vertex is exactly *d*. By Hall's theorem, one can represent such a multigraph as a combination of at most *n*^{2} cycle covers, each taken...

**Remote attribute grammars**

John Tang Boyland

Pages: 627-687

DOI: 10.1145/1082036.1082042

Describing the static semantics of programming languages with attribute grammars is eased when the formalism allows direct dependencies to be induced between rules for nodes arbitrarily far away in the tree. Such *direct non-local* dependencies...

**Boosting textual compression in optimal linear time**

Paolo Ferragina, Raffaele Giancarlo, Giovanni Manzini, Marinella Sciortino

Pages: 688-713

DOI: 10.1145/1082036.1082043

We provide a general boosting technique for Textual Data Compression. Qualitatively, it takes a good compression algorithm and turns it into an algorithm with a better compression performance guarantee. It displays the following remarkable...