Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 4 Issue 4, August 2008

An O(n2.75) algorithm for incremental topological ordering
Deepak Ajwani, Tobias Friedrich, Ulrich Meyer
Article No.: 39
DOI: 10.1145/1383369.1383370

We present a simple algorithm which maintains the topological order of a directed acyclic graph (DAG) with n nodes, under an online edge insertion sequence, in O(n2.75) time, independent of the number m of...

Fully dynamic algorithms for chordal graphs and split graphs
Louis Ibarra
Article No.: 40
DOI: 10.1145/1383369.1383371

We present the first dynamic algorithm that maintains a clique tree representation of a chordal graph and supports the following operations: (1) query whether deleting or inserting an arbitrary edge preserves chordality; and (2) delete or insert...

Dynamic routing schemes for graphs with low local density
Amos Korman, David Peleg
Article No.: 41
DOI: 10.1145/1383369.1383372

This article studies approximate distributed routing schemes on dynamic communication networks. The work focuses on dynamic weighted general graphs where the vertices of the graph are fixed, but the weights of the edges may change. Our main...

Label-guided graph exploration by a finite automaton
Reuven Cohen, Pierre Fraigniaud, David Ilcinkas, Amos Korman, David Peleg
Article No.: 42
DOI: 10.1145/1383369.1383373

A finite automaton, simply referred to as a robot, has to explore a graph, that is, visit all the nodes of the graph. The robot has no a priori knowledge of the topology of the graph, nor of its size. It is known that for any k-state...

Dense subgraph problems with output-density conditions
Akiko Suzuki, Takeshi Tokuyama
Article No.: 43
DOI: 10.1145/1383369.1383374

We consider the dense subgraph problem that extracts a subgraph, with a prescribed number of vertices, having the maximum number of edges (or total edge weight, in the weighted case) in a given graph. We give approximation algorithms with improved...

Deterministic conflict-free coloring for intervals: From offline to online
Amotz Bar-Noy, Panagiotis Cheilaris, Shakhar Smorodinsky
Article No.: 44
DOI: 10.1145/1383369.1383375

We investigate deterministic algorithms for a frequency assignment problem in cellular networks. The problem can be modeled as a special vertex coloring problem for hypergraphs: In every hyperedge there must exist a vertex with a color that occurs...

Improved algorithms for optimal embeddings
Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Mohammad Ali Safari, Amit Sahai
Article No.: 45
DOI: 10.1145/1383369.1383376

In the last decade, the notion of metric embeddings with small distortion has received wide attention in the literature, with applications in combinatorial optimization, discrete mathematics, and bio-informatics. The notion of embedding is, given...

Ordinal embeddings of minimum relaxation: General properties, trees, and ultrametrics
Noga Alon, Mihai Bădoiu, Erik D. Demaine, Martin Farach-Colton, Mohammadtaghi Hajiaghayi, Anastasios Sidiropoulos
Article No.: 46
DOI: 10.1145/1383369.1383377

We introduce a new notion of embedding, called minimum-relaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is the relative order between pairs of distances, and...

A new approximation algorithm for the asymmetric TSP with triangle inequality
Markus Bläser
Article No.: 47
DOI: 10.1145/1383369.1383378

We present a polynomial time factor 0.999 ċ log n approximation algorithm for the asymmetric traveling salesperson problem with triangle inequality.


The relative worst order ratio applied to seat reservation
Joan Boyar, Paul Medvedev
Article No.: 48
DOI: 10.1145/1383369.1383379

The seat reservation problem is the problem of assigning passengers to seats on a train with n seats and k stations enroute in an online manner. The performance of algorithms for this problem is studied using the relative worst order...

Approximation schemes for wireless networks
Tim Nieberg, Johann Hurink, Walter Kern
Article No.: 49
DOI: 10.1145/1383369.1383380

Wireless networks are created by the communication links between a collection of radio transceivers. The nature of wireless transmissions does not lead to arbitrary undirected graphs but to structured graphs which we characterize by the...

Approximation algorithms for a facility location problem with service capacities
Jens Maßberg, Jens Vygen
Article No.: 50
DOI: 10.1145/1383369.1383381

We present the first constant-factor approximation algorithms for the following problem. Given a metric space (V, c), a finite set DV of terminals/customers with demands d : D → R+,...

Fault-tolerant facility location
Chaitanya Swamy, David B. Shmoys
Article No.: 51
DOI: 10.1145/1383369.1383382

We consider a fault-tolerant generalization of the classical uncapacitated facility location problem, where each client j has a requirement that rj distinct facilities serve it, instead of just one. We give a...

Atomic congestion games among coalitions
Dimitris Fotakis, Spyros Kontogiannis, Paul Spirakis
Article No.: 52
DOI: 10.1145/1383369.1383383

We consider algorithmic questions concerning the existence, tractability, and quality of Nash equilibria, in atomic congestion games among users participating in selfish coalitions.

We introduce a coalitional congestion model among atomic...