Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 55 Issue 4, September 2008

The approximability of MAX CSP with fixed-value constraints
Vladimir Deineko, Peter Jonsson, Mikael Klasson, Andrei Krokhin
Article No.: 16
DOI: 10.1145/1391289.1391290

In the maximum constraint satisfaction problem (MAX CSP), one is given a finite collection of (possibly weighted) constraints on overlapping sets of variables, and the goal is to assign values from a given finite domain to the variables so as to...

Undirected connectivity in log-space
Omer Reingold
Article No.: 17
DOI: 10.1145/1391289.1391291

We present a deterministic, log-space algorithm that solves st-connectivity in undirected graphs. The previous bound on the space complexity of undirected st-connectivity was log4/3(⋅) obtained by Armoni, Ta-Shma, Wigderson...

Optimal maintenance of a spanning tree
Baruch Awerbuch, Israel Cidon, Shay Kutten
Article No.: 18
DOI: 10.1145/1391289.1391292

In this article, we show that keeping track of history enables significant improvements in the communication complexity of dynamic network protocols. We present a communication optimal maintenance of a spanning tree in a dynamic network. The...

Semantic subtyping: Dealing set-theoretically with function, union, intersection, and negation types
Alain Frisch, Giuseppe Castagna, Véronique Benzaken
Article No.: 19
DOI: 10.1145/1391289.1391293

Subtyping relations are usually defined either syntactically by a formal system or semantically by an interpretation of types into an untyped denotational model. This work shows how to define a subtyping relation semantically in the presence of...