Information Processing Letters, Volume 65

Volume 65, Number 1, 15 January 1998

Venkatesh Raman, Bala Ravikumar, S. Srinivasa Rao:
A Simplified NP-Complete MAXSAT Problem. 1-6
Peter Y. A. Ryan, Steve A. Schneider:
An Attack on a Recursive Authentication Protocol. A Cautionary Tale. 7-10
Jamel Lakhal, Luc Litzler:
A Polynomial Algorithm for the Extendability Problem in Bipartite Graphs. 11-16
Paul E. Dunne, Michele Zito:
An Inproved Upper Bound on the Non-3-Colourability Threshold. 17-23
Carlo Blundo, Alfredo De Santis, Ugo Vaccaro:
On Secret Sharing Schemes. 25-32
Amos Israeli, Asaf Shirazi:
The Time Complexity of Updating Snapshot Memories. 33-40
Hosam M. Mahmoud:
On Rotations in Fringe-Balanced Binary Trees. 41-46
Refik Molva, Gene Tsudik:
Secret Sets and Applications. 47-55

Teodor Knapik, Étienne Payet:
The Full Quotient and its Closure Property for Regular Languages. 57-62
Ahmed Ait-Bouziad, Helen Kassel:
An Inproved Algorithm for Retrieving Fuzzy Information from Two Systems. 63-66
Michiel A. Odijk, Hans van Maaren:
Improved Solutions to the Steiner Triple Covering Problem. 67-69
Gwoboa Horng:
An Active Attack on Protocols for Server-Aided RSA Signature Computation. 71-73
T. C. Edwin Cheng, Qing Ding:
The Complexity of Scheduling Starting Time Dependent Tasks with Release Times. 75-79
Jou-Ming Chang, Chin-Wen Ho:
The Recognition of Geodetically Connected Graphs. 81-88
Peter J. Grabner, Helmut Prodinger:
An Asymptotic Study of a Recursion Occurring in the Analysis of an Algorithm on Broadcast Communication. 89-93
Michael Segal, Klara Kedem:
Enclosing k Points in the Smallest Axis Parallel Rectangle. 95-99
Dimitrios Dervos, Yannis Manolopoulos, P. Linardis:
Comparison of Signature File Models with Superimposed Coding. 101-106
Anders Dessmark, Oscar Garrido, Andrzej Lingas:
A Note on Parallel Complexity of Maximum f-Matching. 107-109
Therese C. Biedl:
Relating Bends and Size in Orthogonal Graph Drawings. 111-115

Sunil Arya, H. Ramesh:
A 2.5-Factor Approximation Algorithm for the k-MST Problem. 117-118
Q. S. Wu, Kun-Mao Chao, Richard C. T. Lee:
The NPO-Completeness of the Longest Hamiltonian Cycle Problem. 119-123
Pallab Dasgupta:
Agreement under Faulty Interfaces. 125-129
Shiva Chaudhuri, Naveen Garg, R. Ravi:
The p-Neighbor k-Center Problem. 131-134
Limin Xiang, Kazuo Ushijima:
ANSV Problem on BSRs. 135-138
Jung Je Son, Jong In Lim, Seongtaek Chee, Soo Hak Sung:
Global Avalanche Characteristics and Nonlinearity of Balanced Boolean Functions. 139-144
Viggo Kann, Jens Lagergren, Alessandro Panconesi:
Approximate Max k-Cut with Subgraph Guarantee. 145-150
Edith Hemaspaandra, Jörg Rothe:
Recognizing when Greed can Approximate Maximum Independent Sets is Complete for Parallel Access to NP. 151-156
Jeng-Jung Wang, Chun-Nan Hung, Lih-Hsing Hsu:
Optimal 1-Hamiltonian Graphs. 157-161
R. Balasubramanian, Michael R. Fellows, Venkatesh Raman:
An Improved Fixed-Parameter Algorithm for Vertex Cover. 163-168

Kim S. Larsen:
Regular Expressions with Nested Levels of Back Referencing Form a Hierarchy. 169-172
Jerzy R. Nawrocki, Adam Czajka, Wojciech Complak:
Scheduling Cyclic Tasks with Binary Periods. 173-178
Sundarajan Vedantham, S. Sitharama Iyengar:
The Bandwidth Allocation Problem in the ATM Network Model is NP-Complete. 179-182
Stavros D. Nikolopoulos, Panos Rondogiannis:
On the Number of Spanning Trees of Multi-Star Related Graphs. 183-188
Tzonelih Hwang, Chih-Hung Wang:
Arbetrated Unconditionally Secure Authentication Scheme with Multi-Senders. 189-193
Luc Devroye:
On the Richness of the Collection of Subtrees in Random Binary Search Trees. 195-199
Chung Keung Poon, Binhai Zhu, Francis Y. L. Chin:
A Polynomial Time Solution for Labeling a Rectlinear Map. 201-207
Oded Shmueli, Kurt A. Shoens:
Data Sufficiency for Queries on Cache. 209-216
Nader H. Bshouty, Christino Tamon, David K. Wilson:
On Learning width Two Branching Programs. 217-222

Yair Amir, Avishai Wool:
Optimal Availability Quorum Systems: Theory and Practice. 223-228
Paolo Dell'Olmo, Hans Kellerer, Maria Grazia Speranza, Zsolt Tuza:
A 13/12 Approximation Algorithm for Bin Packing with Extendable Bins. 229-233
James F. Korsh, Seymour Lipschutz:
Shifts and Loopless Generation of k-Ary Trees. 235-240
Jeremy Frank, Ian P. Gent, Toby Walsh:
Asymptotic and Finite Size Parameters for Phase Transitions: Hamiltonian Circuit as a Case Study. 241-245
Heung-Taek Kim, Myoung-Ho Kim:
Starvation-Free Secure Multiversion Concurrency Control. 247-253
D. J. Guan:
An Optimal Message Routing Algorithm for Double-Loop Networks. 255-260
Wen-Huei Chen:
Test Sequence Generation from the Protocol Data Portion Based on the Selecting Chinese Postman Algorithm. 261-268
Danny Z. Chen, Ovidiu Daescu:
Maintaining Visibility of a Polygon with a Moving Point of View. 269-275
Prosenjit Bose, Jonathan F. Buss, Anna Lubiw:
Pattern Matching for Permutations. 277-283

William McCune:
Automatic Proofs and Counterexamples for Some Ortholattice Identities. 285-291
Alberto Del Lungo, Maurice Nivat, Renzo Pinzani, L. Sorri:
The Medians of Discrete Sets. 293-299
Elias Dahlhaus, Paul D. Manuel, Mirka Miller:
Maximum h-Colourable Subgraph Problem in Balanced Graphs. 301-303
Gunnar Andersson, Lars Engebretsen:
Better Approximation Algorithms for SET SPLITTING and NOT-ALL-EQUAL SAT. 305-311
Philippe Herrmann:
Timed Automata and Recognizability. 313-318
Kaijung Chang, Yan Huat Tan, Yaakov L. Varol, Jiang-Hsing Chu:
A Study on Interleaving Versus Segmentation. 319-324
Shing-Tsaan Huang, Tzong-Jye Liu:
Four-State Stabilizing Phase Clock for Unidirectional Rings of Odd Size. 325-329
Yaw-Wen Chang, Chang-Biau Yang:
A Parallel Algorithm for Circulant Tridiagonal Linear Systems. 331-337

Last update Thu May 23 19:00:35 2013 CET by the DBLP Team —

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