Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 44 Issue 5, Sept. 1997

Applications of a logic of knowledge to motion planning under uncertainty
Ronen I. Brafman, Jean-Claude Latombe, Yoram Moses, Yoav Shoham
Pages: 633-668
DOI: 10.1145/265910.265912
Inspired by the success of the distributed computing community in apply logics of knowledge and time to reasoning about distributed protocols, we aim for a similarly powerful and high-level abstraction when reasoning about control problems...

Sparsification—a technique for speeding up dynamic graph algorithms
David Eppstein, Zvi Galil, Giuseppe F. Italiano, Amnon Nissenzweig
Pages: 669-696
DOI: 10.1145/265910.265914
We provide data strutures that maintain a graph as edges are inserted and deleted, and keep track of the following properties with the following times: minimum spanning forests, graph connectivity, graph 2-edge connectivity, and bipartiteness in...

Learning to reason
Roni Khardon, Dan Roth
Pages: 697-725
DOI: 10.1145/265910.265918
We introduce a new framework for the study of reasoning. The Learning (in order) to Reason approach developed here views learning as an integral part of the inference process, and suggests that learning and reasoning should be studied...

How much can hardware help routing?
Allan Borodin, Prabhakar Raghavan, Baruch Schieber, Eli Upfal
Pages: 726-741
DOI: 10.1145/265910.265922
We study the extent to which complex hardware can speed up routing. Specifically, we consider the following questions. How much does adaptive routing improve over oblivious routing? How much does randomness help? How does it help if each node...

Time-work tradeoffs for parallel algorithms
Thomas H. Spencer
Pages: 742-778
DOI: 10.1145/265910.265923
Some parallel algorithms have the property that, as they are allowed to take more time, the total work that they do is reduced. This paper describes several algorithms with this property. These algorithms solve important problems on directed...