Search ACM DL

Search Issue

enter search term and/or author name

**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* = {(*S*_{1}, *T*_{1}), …, (*S*_{k},...

**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 *s*_{1},…,*s*_{k} 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...