Information Processing Letters, Volume 32

Volume 32, Number 1, July 1989

Peter Damaschke:
The Hamiltonian Circuit Problem for Circle Graphs is NP-Complete. 1-2
Dilip Sarkar, Ivan Stojmenovic:
An Optimal Parallel Circle-Cover Algorithm. 3-6
Neil J. Gunther:
Path Integral Methods for Computer Performance Analysis. 7-13
Jirí Matousek:
On-Line Computation of Convolutions. 15-16
A. Prasad Sistla:
On Verifying that a Concurrent Program Satisfies a Nondeterministic Specification. 17-23
Kazuo Iwano:
An Improvement of Goldberg, Plotkin and Vaidya's Maximal Node-Disjoint Paths Algorithm. 25-27
Joachim Biskup:
Boyce-Codd Normal Form and Object Normal Forms. 29-33
Torben Hagerup:
Hybridsort Revisited and Parallelized. 35-39
Andreas Blass, Yuri Gurevich:
On Matijasevitch's Nontraditional Approach to Search Problems. 41-45
Errol L. Lloyd:
A Fast Algorithm for Finding Interlocking Sets. 47-50

Hwang Kyu Choi, Myunghwan Kim:
Hybrid Join: An Improved Sort-Based Join Algorithm. 51-56
Laurence Boxer, Russ Miller:
A Parallel Circle-Cover Minimization Algorithm. 57-60
Maw-Sheng Chern, Gen-Huey Chen, Pangfeng Liu:
An LC Branch-and-Branch Algorithm for the Module Assignment Problem. 61-71
Young J. Kim, Gil C. Kim:
Coordinator: A Modification to the Monitor Concept. 73-80
Dror G. Feitelson, Larry Rudolph:
Implementation of a Wait-Free Synchronization Primitive that Solves n-Process Consensus. 81-83
David A. Wolfram:
Forward Checking and Intelligent Backtracking. 85-87
Y. C. Chen, Z. C. Yen, G. H. Chen:
Using Fewer Processors to Reduce Time Complexities of Semigroup Computations. 89-93

David B. Skillicorn, David T. Barnard:
Parallel parsing on the connection machine. 111-117
Satoshi Matsuoka, Tomihisa Kamada, Satoru Kawai:
Asymptotic evaluation of window visibility. 119-126
Gerard Tel, Friedemann Mattern:
Comments on "ring based termination detection algorithm for distributed computations". 127-128
Wei Kuan Shih, Wen-Lian Hsu:
An O(n log n + m log log n) maximum weight clique algorithm for circular-arc graphs. 129-134
Hans L. Bodlaender:
Achromatic number is NP-complete for cographs and interval graphs. 135-138
John N. Tsitsiklis:
On the use of random numbers in asynchronous simulation via rollback. 139-144
Joseph Y.-T. Leung:
Bin packing with restricted piece sizes. 145-149
Patrick Lentfert, Mark H. Overmars:
Data structures in a real-time environment. 151-155
Joseph Cheriyan, S. N. Maheshwari:
The parallel complexity of finding a blocking flow in a 3-layer network. 157-161
Martin Beaudry:
Characterization of idempotent transformation monoids. 163-166

Mikhail J. Atallah, Danny Z. Chen:
An Optimal Parallel Algorithm for the Minimum Circle-Cover Problem. 159-165
Giri Narasimhan:
A Note on the Hamiltonian Circuit Problem on Directed Path Graphs. 167-170
Marshall W. Bern, Paul E. Plassmann:
The Steiner Problem with Edge Lengths 1 and 2. 171-176
Gerard Ligozat, Helene Bestougeff:
On Relations Between Intervals. 177-182
Mohan B. Sharma, S. Sitharama Iyengar:
An Efficient Distributed Depth-First-Search Algorithm. 183-186
, Corrigenda: IPL 35(1): 55-56 (1990)
Micha Sharir:
A Note on the Papadimitriou-Silverberg Algorithm for Planning Optimal Piecewise-Linear Motion of a Ladder. 187-190
Andrzej Lingas:
Voronoi Diagrams with Barriers and the Shortest Diagonal Problem. 191-198
John A. Ellis, Manrique Mata, Gary MacGillivray:
A Linear Time Algorithm for Longest (s,t)-Paths in Weighted Outer Planar Graphs. 199-204
Ömer Egecioglu, Bahman Kalantari:
Approximating the Diameter of a Set of Points in the Euclidean Space. 205-211
Ravi S. Sandhu:
The Demand Operation in the Schematic Protection Model. 213-219

Jan van den Bos:
PROCOL: A Protocol-Constrained Concurrent Object-Oriented Language. 221-227
Rainer Kemp:
A One-to-One Correspondence between two Classes of Ordered Trees. 229-234
Nissim Francez:
Cooperating Proofs for Distributed Programs with Multiparty Interactions. 235-242
, Corrigenda: IPL 34(1): 57 (1990), IPL 35(5): 275 (1990)
Hazel Everett, A. Gupta:
Acyclic Directed Hypercubes may have Exponential Diameter. 243-245
Grant A. Cheston, Arthur M. Farley, Stephen T. Hedetniemi, Andrzej Proskurowski:
Centering a Spanning Tree of a Biconnected Graph. 247-250
David A. Mix Barrington, James C. Corbett:
On the Relative Complexity of Some Languages in NC. 251-256
A. Clouatre, Normand Laliberte, T. H. Merrett:
A General Implementation of Relational Recursion with Speedup Techniques for Programmers. 257-262
George H. Roberts:
Another Note on Recursive Ascent. 263-266
Gerd Baron, Friedrich J. Urbanek:
Factorial Languages with Quadratically Upper Bounded Growth Functions and Nonlinearly Upper Bounded Subword Complexities. 267-269
Erkki Mäkinen:
On the Subtree Isomorphism Problem for Ordered Trees. 271-273
P. P. Chakrabarti, Sujoy Ghose, A. Pandey, S. C. De Sarkar:
Increasing Search Efficiency Using Multiple Heuristics. 275

Shuji Shiraishi:
A Parallel Algorithm for the Maximum 2-Chain Edge Packing Problem. 277-279
Serge Abiteboul:
Boundedness is Undecidable for Datalog Programs with a Single Recursive Rule. 281-287
Henk Alblas:
Optimal Incremental Simple Multi-Pass Attribute Evaluation. 289-295
Manfred Padberg, Antonio Sassano:
The Complexity of Matching with Bonds. 297-300
Robert L. (Scot) Drysdale III, Jerzy W. Jaromczyk:
A Note on Lower Bounds for the Maximum Area and Maximum Perimeter (kappa)k-gon Problems. 301-303
Alan Gibbons, Y. N. Srikant:
A Class of Problems Efficiently Solvable on Mesh-Connected Computers Including Dynamic Expression Evaluation. 305-311
Robert Demolombe, Arantza Illarramendi:
Heuristics for Syntactial Optimization of Relational Queries. 313-316
Serge Abiteboul, Marc Gyssens, Dirk Van Gucht:
An Alternative Way to Represent the Cogroup of a Relation in the Context of Nested Databases. 317-324
Yoshihito Toyama:
Fast Knuth-Bendix Completion with a Term Rewriting System Compiler. 325-328

Last update Tue Feb 14 04:19:34 2012 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page