Mathematical Systems Theory, Volume 24

Volume 24, Number 1, 1991

Osamu Watanabe: On Intractability of the Class UP. 1-10 BibTeX
Zevi Miller, Ivan Hal Sudborough: A Polynomial Algorithm for Recognizing Bounded Cutwidth in Hypergraphs. 11-40 BibTeX
Juraj Hromkovic: On Problems for Which no Oracle Can Help. 41-52 BibTeX
Eric Allender: Limitations of the Upward Separation Technique. 53-67 BibTeX

Seinosuke Toda: On Polynomial-Time Truth-Table Reducibility of Intractable Sets to P-Selective Sets. 68-82 BibTeX
Antoni Lozano, Jacobo Torán: Self-Reducible Sets of Small Sensity. 83-100 BibTeX
Ian Parberry: A Computer-Assisted Optimal Depth Lower Bound for Nine-Input Sorting Networks. 101-116 BibTeX
Bruno Courcelle, Damian Niwinski, Andreas Podelski: A Geometrical View of the Determinization and Minimization of Finite-State Automata. 117-146 BibTeX

William Slough, Karl Winklmann: On Limitations of Transformations Between Combinatorial Problems. 149-168 BibTeX
James Haralambides, Fillia Makedon, Burkhard Monien: Bandwidth Minimization: An Approximation Algorithm for Caterpillars. 169-177 BibTeX
Harry Buhrman, Steven Homer, Leen Torenvliet: Completeness for Nondeterministic Complexity Classes. 179-200 BibTeX
Dina Kravets, James K. Park: Selection and Sorting in Totally Monotone Arrays. 201-220 BibTeX

Christos Kaklamanis, Danny Krizanc, Thanasis Tsantilas: Tight Bounds for Oblivious Routing in the Hypercube. 223-232 BibTeX
Marc Baumslag, Fred S. Annexstein: A Unified Framework for Off-Line Permutation Routing in Parallel Networks. 233-251 BibTeX
William Aiello, Frank Thomson Leighton, Bruce M. Maggs, Mark Newman: Fast Algorithms for Bit-Serial Routing on a Hypercube. 253-271 BibTeX
Yuh-Dauh Lyuu: Fast Fault-Tolerant Parallel Communication and On-Line Maintenance for Hypercubes Using Information Dispersal. 273-294 BibTeX
David S. Greenberg, Sandeep N. Bhatt: Routing Multiple Paths in Hypercubes. 295-321 BibTeX