By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 27, Issue 3, pp. 605-915

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Listing all Minimal Separators of a Graph

T. Kloks and D. Kratsch

pp. 605-613

BibTeX  Abstract Full Text:  PDF

Efficient Self-Embedding of Butterfly Networks with Random Faults

Hisao Tamaki

pp. 614-636

BibTeX  Abstract Full Text:  PDF

Splittings, Robustness, and Structure of Complete Sets

Harry Buhrman, Albrecht Hoene, and Leen Torenvliet

pp. 637-653

BibTeX  Abstract Full Text:  PDF

Constructing Levels in Arrangements and Higher Order Voronoi Diagrams

Pankaj K. Agarwal, Mark de Berg, Jirí Matousek, and Otfried Schwarzkopf

pp. 654-667

BibTeX  Abstract Full Text:  PDF

A Constant Time Optimal Parallel Algorithm for Two-Dimensional Pattern Matching

Maxime Crochemore, Leszek Gasieniec, Ramesh Hariharan, S. Muthukrishnan, and Wojciech Rytter

pp. 668-681

BibTeX  Abstract Full Text:  PDF

Improved Randomized On-Line Algorithms for the List Update Problem

Susanne Albers

pp. 682-693

BibTeX  Abstract Full Text:  PDF

Computing the Additive Complexity of Algebraic Circuits with Root Extracting

Dima Grigoriev and Marek Karpinski

pp. 694-701

BibTeX  Abstract Full Text:  PDF

An $\Omega(D\log (N/D))$ Lower Bound for Broadcast in Radio Networks

Eyal Kushilevitz and Yishay Mansour

pp. 702-712

BibTeX  Abstract Full Text:  PDF

Optimal On-Line Search and Sublinear Time Update in String Matching

Paolo Ferragina and Roberto Grossi

pp. 713-736

BibTeX  Abstract Full Text:  PDF
SPECIAL SECTION

Introduction to Special Section on Probabilistic Proof Systems

Shafi Goldwasser

pp. 737-738

BibTeX  Abstract Full Text:  PDF

On the Power of Finite Automata with both Nondeterministic and Probabilistic States

Anne Condon, Lisa Hellerstein, Samuel Pottle, and Avi Wigderson

pp. 739-762

BibTeX  Abstract Full Text:  PDF

A Parallel Repetition Theorem

Ran Raz

pp. 763-803

BibTeX  Abstract Full Text:  PDF

Free Bits, PCPs, and Nonapproximability---Towards Tight Results

Mihir Bellare, Oded Goldreich, and Madhu Sudan

pp. 804-915

BibTeX  Abstract Full Text:  PDF