Search ACM DL

Search Issue

enter search term and/or author name

**An O(n^{2.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*(*n*^{2.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 *D* ⊆ *V* 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 *r*_{j} *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...