ACM DL

Algorithms (TALG)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Algorithms (TALG), Volume 7 Issue 2, March 2011

Data structures for mergeable trees
Loukas Georgiadis, Haim Kaplan, Nira Shafrir, Robert E. Tarjan, Renato F. Werneck
Article No.: 14
DOI: 10.1145/1921659.1921660

Motivated by an application in computational geometry, we consider a novel variant of the problem of efficiently maintaining a forest of dynamic rooted trees. This variant includes an operation that merges two tree paths. In contrast to the...

Decision trees for entity identification: Approximation algorithms and hardness results
Venkatesan T. Chakaravarthy, Vinayaka Pandit, Sambuddha Roy, Pranjal Awasthi, Mukesh K. Mohania
Article No.: 15
DOI: 10.1145/1921659.1921661

We consider the problem of constructing decision trees for entity identification from a given relational table. The input is a table containing information about a set of entities over a fixed set of attributes and a probability distribution over...

Constant factor approximations for the hotlink assignment problem
Tobias Jacobs
Article No.: 16
DOI: 10.1145/1921659.1921662

The concept of hotlink assignment aims at reducing the navigation effort for the users of a Web directory or similar structure by inserting a limited number of additional hyperlinks called hotlinks. The k-hotlink assignment...

Tree exploration with logarithmic memory
Christoph Ambühl, Leszek Gąsieniec, Andrzej Pelc, Tomasz Radzik, Xiaohui Zhang
Article No.: 17
DOI: 10.1145/1921659.1921663

We consider the task of network exploration by a mobile agent (robot) with small memory. The agent has to traverse all nodes and edges of a network (represented as an undirected connected graph), and return to the starting node. Nodes of the...

Set connectivity problems in undirected graphs and the directed steiner network problem
Chandra Chekuri, Guy Even, Anupam Gupta, Danny Segev
Article No.: 18
DOI: 10.1145/1921659.1921664

In the generalized connectivity problem, we are given an edge-weighted graph G = (V,E) and a collection D = {(S1, T1), …, (Sk,...

Shortest vertex-disjoint two-face paths in planar graphs
Éric Colin De Verdière, Alexander Schrijver
Article No.: 19
DOI: 10.1145/1921659.1921665

Let G be a directed planar graph of complexity n, each arc having a nonnegative length. Let s and t be two distinct faces of G let s1,…,sk be vertices incident...

Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
Michael Elkin
Article No.: 20
DOI: 10.1145/1921659.1921666

We present a streaming algorithm for constructing sparse spanners and show that our algorithm significantly outperforms the state-of-the-art algorithm for this task (due to Feigenbaum et al.). Specifically, the processing time per edge of our...

Algorithms for distributed functional monitoring
Graham Cormode, S. Muthukrishnan, Ke Yi
Article No.: 21
DOI: 10.1145/1921659.1921667

Consider the following problem: We have k players each receiving a stream of items, and communicating with a central coordinator. Let the multiset of items received by player i up until time t be...

Sum edge coloring of multigraphs via configuration LP
Magnús M. Halldórsson, Guy Kortsarz, Maxim Sviridenko
Article No.: 22
DOI: 10.1145/1921659.1921668

We consider the scheduling of biprocessor jobs under sum objective (BPSMSM). Given a collection of unit-length jobs where each job requires the use of two processors, find a schedule such that no two jobs involving the same processor run...

Competitive analysis of flash memory algorithms
Avraham Ben-Aroya, Sivan Toledo
Article No.: 23
DOI: 10.1145/1921659.1921669

Flash memories are widely used in computer systems ranging from embedded systems to workstations and servers to digital cameras and mobile phones. The memory cells of flash devices can only endure a limited number of write cycles, usually between...

Finding witnesses by peeling
Yonatan Aumann, Moshe Lewenstein, Noa Lewenstein, Dekel Tsur
Article No.: 24
DOI: 10.1145/1921659.1921670

In the k-matches problem, we are given a pattern and a text, and for each text location, the desired output consists of all aligned matching characters if there are k or fewer of them, and any k aligned matching characters if...

Constrained pattern matching
Yongwook Choi, Wojciech Szpankowski
Article No.: 25
DOI: 10.1145/1921659.1921671

Constrained sequences are strings satisfying certain additional structural restrictions (e.g., some patterns are forbidden). They find applications in communication, digital recording, and biology. In this article, we restrict our attention to the...

Discovering almost any hidden motif from multiple sequences
Bin Fu, Ming-Yang Kao, Lusheng Wang
Article No.: 26
DOI: 10.1145/1921659.1921672

We study a natural probabilistic model for motif discovery. In this model, there are k background sequences, and each character in a background sequence is a random character from an alphabet Σ. A motif...

Computing the inverse sort transform in linear time
Ge Nong, Sen Zhang, Wai Hong Chan
Article No.: 27
DOI: 10.1145/1921659.1921673

The Sort Transform (ST) can significantly speed up the block sorting phase of the Burrows-Wheeler Transform (BWT) by sorting the limited order contexts. However, the best result obtained so far for the inverse ST has a time complexity...