Information Processing Letters, Volume 40

Volume 40, Number 1, 11 October 1991

Pierluigi Crescenzi, C. Fiorini, Riccardo Silvestri:
A Note on the Approximation of the MAX CLIQUE Problem. 1-5
Reinhold Heckmann:
Lower and Upper Power Domain Constructions Commute on all Cpos. 7-11
Nen-Fu Huang, Ching-Ho Huang:
Complexity of the Repeaters Allocating Problem. 13-20
Volker Diekert, Ronald V. Book:
On ``Inherently Context-Sensitive'' Languages - An Application of Complexity Cores. 21-23
Tao Jiang, Bala Ravikumar:
A Note on the Space Complexity of Some Decision Problems for Finite Automata. 25-31
Maria Cristina Pinotti, Geppino Pucci:
Parallel Priority Queues. 33-40
Thomas C. Shermer:
A Counterexample to the Algorithms for Determining Opaque Minimal Forests. 41-42
Jean R. S. Blair, Errol L. Lloyd:
The Benefits of External Wires in Single Row Routing. 43-49
Wim H. Hesselink:
Repetitions, Known or Unknown? 51-57

Ravi Janardan:
On the Dynamic Maintenance of Maximal Points in the Plane. 59-64
Victor Yodaiken:
Modal Functions for Concise Definition of State Machines and Products. 65-72
Staffan Bonnier, Ulf Nilsson, Torbjörn Näslund:
A Simple Fixed Point Characterization of Three-Valued Stable Model Semantics. 73-78
Victor Y. Pan, John H. Reif:
The Parallel Computation of Minimum Cost Paths in Graphs by Stream Contraction. 79-83
Yi Xian Yang:
New Enumeration Results About the Optical Orthogonal Codes. 85-87
Eric Allender, Vivek Gore:
Rudimentary Reductions Revisited. 89-95
R. V. Subramaniyam, A. A. Diwan:
A Counterexample for the Sufficiency of Edge Guards in Star Polygons. 97-99
Xiaodong Wang:
On the Complexity of the Extreme Points Decision Problem. 101-106
Ruay Shiung Chang:
Single Step Graph Search Problem. 107-111
Jonathan Brandt, Carlos Cabrelli, Ursula Molter:
An Algorithm for the Computation of the Hutchinson Distance. 113-117

Alok Aggarwal, Prabhakar Raghavan:
Deferred Data Structure for the Nearest Neighbor Problem. 119-122
Wen-Lian Hsu, Kuo-Hui Tsai:
Linear Time Algorithms on Circular-Arc Graphs. 123-129
Sylvia C. Boyd, Hasan Ural:
The Synchronization Problem in Protocol Testing and its Complexity. 131-136
Shashank K. Mehta, Maharaj Mukherjee, George Nagy:
Constrained Integer Approximation to Planar Line Intersection. 137-139
Martín Abadi, Bowen Alpern, Krzysztof R. Apt, Nissim Francez, Shmuel Katz, Leslie Lamport, Fred B. Schneider:
Preserving Liveness: Comments on ``Safety and Liveness from a Methodological Point of View''. 141-142
Frank Dederichs, Rainer Weber:
Reply to the Comments by Martín Abadi et al. 143
Wen-Huei Chen, Chuan Yi Tang:
Computing the Optimal IO Sequences of a Protocol in Polynomial Time. 145-148
Richard C. Brewster, Gary MacGillivray:
A Note on Restricted H-Colouring. 149-151
Sukumar Ghosh:
Binary Self-Stabilization in Distributed Systems. 153-159
Joel Wein:
Las Vegas RNC Algorithms for Unary Weighted Perfect Matching and T-Join Problems. 161-167
Andrzej Pelc:
Broadcasting in Complete Networks with Faulty Nodes Using Unreliable Calls. 169-174

Jeffrey K. Uhlmann:
Satisfying General Proximity/Similarity Queries with Metric Trees. 175-179
Teofilo F. Gonzalez:
Covering a Set of Points in Multidimensional Space. 181-188
Dan Halperin, Micha Sharir:
On Disjoint Concave Chains in Arrangements of (Pseudo) Lines. 189-192
Bin Jiang:
DFS-Traversing Graphs in a Paging Environment, LRU or MRU? 193-196
Stefan Rönn:
On the Logarithmic Evaluation of Recurrence Relations. 197-199
Do-Hyung Kim, Kwang-Moo Choe:
Yet Another Efficient Backward Execution Algorithm in the AND/OR Process Model. 201-211
Thierry Massart:
An Agent Calculus with Simple Actions Where the Enabling and Disabling are Derived Operators. 213-218
Ferroudja Cherief, Ph. Schnoebelen:
\tau-Bisimulations and Full Abstraction for Refinement of Actions. 219-222
Rong Lin:
Fast Algorithms for Lowest Common Ancestors on a Processor Array with Reconfigurable Buses. 223-230

Jimmi S. Pettersson:
Comments on ``Always-True is not Invariant'': Assertional Reasoning About Invariance. 231-233
Josep Domingo-Ferrer:
Distributed User Identification by Zero-Knowledge Access Rights Proving. 235-239
Zhi-Zhong Chen:
A Randomized NC Algorithm for the Maximal Tree Cover Problem. 241-246
James K. Park:
A Special Case of the n-Vertex Traveling-Salesman Problem that can be Solved in O(n) Time. 247-254
Roberto Grossi:
Further Comments on the Subtree Isomorphism for Ordered Trees. 255-256
Rabi N. Mahapatra, Harish Pareek:
Modelling a Fast Parallel Thinning Algorithm for Shared Memory SIMD Computers. 257-261
Iain A. Stewart:
Complete Problems for Symmetric Logspace Involving Free Groups. 263-267
Zhou Chaochen, C. A. R. Hoare, Anders P. Ravn:
A Calculus of Durations. 269-276
Sumanta Guha, Arunabha Sen:
Expected Time Analysis of Interpolation Merge - A Simple New Merging Algorithm. 277-281
Ju Yuan Hsiao, Chuan Yi Tang, Ruay Shiung Chang:
Solving the Single Step Graph Searching Problem by Solving the Maximum Two-Independent Set Problem. 283-287

Miklós Bartha, Éva Gombás:
A Structure Theorem for Maximum Internal Matchings in Graphs. 289-294
Chang-Biau Yang:
Reducing Conflict Resolution Time for Solving Graph Problems in Broadcast Communications. 295-302
Ferruccio Barsi:
Mod m Arithmetic in Binary Systems. 303-309
Akhil Kumar, Shun Yan Cheung:
A High Availability \sqrt{N} Hierarchical Grid Algorithm for Replicated Data. 311-316
Lloyd Allison, Trevor I. Dix, Chut N. Yee:
Shortest Path and Closure Algorithms for Banded Matrices. 317-322
Xiaojun Shen, Edward M. Reingold:
Scheduling on a Hypercube. 323-328
Pai-Cheng Chu:
Evaluating Clustering Factor Approach to Estimating Block Selectivities. 329-334
Subrata Ghosh, Ambuj Mahanti:
Bidirectional Heuristic Search with Limited Resources. 335-340
Fikret Erçal:
Distributed Evaluation of an Iterative Function for all Object Pairs on an SIMD Hybercube. 341-345

Last update Sat May 18 20:36:40 2013 CET by the DBLP Team —

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