enter search term and/or author name
An O(n2.75) algorithm for incremental topological ordering
Deepak Ajwani, Tobias Friedrich, Ulrich Meyer
Article No.: 39
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
Article No.: 40
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
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...
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
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
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...
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
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
Article No.: 47
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
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...
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
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+,...
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...
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...