Information Processing Letters, Volume 61

Volume 61, Number 1, 14 January 1997

Yongge Wang:
NP-Hard Sets are Superterse Unless NP is Small. 1-6
Martin Farach, S. Muthukrishnan:
Optimal Parallel Randomized Renaming. 7-10
Gow-Hsing King, Wen-Guey Tzeng:
On-Line Algorithms for the Dominating Set Problem. 11-14
Jacob Kornerup:
Odd-Even Sort in Powerlists. 15-24
Toru Hasunuma, Yukio Shibata:
Containment of Butterflies in Networks Constructed by the Line Digraph Operation. 25-30
Sidi Mohamed Sedjelmaci, Christian Lavault:
Improvements on the Accelerated Integer GCD Algorithm. 31-36
Panayiotis Bozanis, Nectarios Kitsios, Christos Makris, Athanasios K. Tsakalidis:
The Space-Optimal Version of a Known Rectangle Enclosure Reporting Algorithm. 37-41
Yaagoub Ashir, Iain A. Stewart, Aqeel Ahmed:
Communication Algorithms in k-Ary n-Cube Interconnection Networks. 43-48
Avrim Blum, David R. Karger:
An Õ(n^{3/14})-Coloring Algorithm for 3-Colorable Graphs. 49-53
Steve Taylor, Nabil I. Hachem, Stanley M. Selkow:
The Average Height of a Node in the BANG Abstract Directory Tree. 55-61

Richard Zippel:
Zero Testing of Algebraic Functions. 63-67
Bernd Loescher:
One Unary Function Says Less Than Two in Existential Second Order Logic. 69-75
D. J. Guan, Xuding Zhu:
A Coloring Problem for Weighted Graphs. 77-81
Ryuhei Uehara:
Collapse of PP with a Semi-Random Source to BPP. 83-87
Youssef Saab:
An Improved Algorithm for Intersecting Convex Polygons. 89-90
Kayoko Shikishima-Tsuji, Masashi Katsura, Yuji Kobayashi:
On Termination of Confluent One-Rule String-Rewriting Systems. 91-96
Kuo-Ling Chung:
Efficient Huffman Decoding. 97-99
Hans L. Bodlaender, Dimitrios M. Thilikos, Koichi Yamazaki:
It is Hard to Know when Greedy is Good for Finding Independent Sets. 101-111
Chin Lung Lu, Chuan Yi Tang:
A Linear-Time Algorithm for the Weighted Feedback Vertex Problem on Interval Graphs. 107-111
Paolo Giulio Franciosa, Giorgio Gambosi, Umberto Nanni:
The Incremental Maintenance of a Depth-First-Search Tree in Directed Acyclic Graphs. 113-120

Jitender S. Deogun, Dieter Kratsch, George Steiner:
An Approximation Algorithm for Clustering Graphs with Dominating Diametral Path. 121-127
Thierry Lecroq, Guillaume Luce, Jean Frédéric Myoupo:
A Faster Linear Systolic Algorithm for Recovering a Longest Common Subsequence. 129-136
Raffaele Mosca:
Polynomial Algorithms for the Maximum Stable Set Problem on Particular Classes of P_5-Free Graphs. 137-143
Guochuan Zhang:
A Simple Semi On-Line Algorithm for P2//C_{max} with a Buffer. 145-148
Seok-Hee Hong, Myoung-Ho Kim:
Resolving Data Conflicts with Multiple Versions and Precedence Relationships in Real-Time Databases. 149-156
Ivan Fris, Ivan Havel, Petr Liebl:
The Diameter of the Cube-Connected Cycles. 157-160
Arnold Rosenbloom:
Monotone Real Circuits are More Powerful than Monotone Boolean Circuits. 161-164
M. Z. Wang:
Linear Complexity Profiles and Jump Complexity. 165-168
Tadakazu Sato:
Ergodicity of Linear Cellular Automata over ganzen Zahlen_m. 169-172

Shih-Yih Wang, Lih-Hsing Hsu, Ting-Yi Sung:
Faithful 1-Edge Fault Tolerant Graphs. 173-181
Martin Henk:
Note on Shortest and Nearest Lattice Vectors. 183-188
Patrizio Cintioli, Riccardo Silvestri:
Revisiting a Result of Ko. 189-194
Paolo Dell'Olmo, Stefano Giordani, Maria Grazia Speranza:
An Approximation Result for a Duo-Processor Task Scheduling Problem. 195-200
Mark J. Encarnación:
Black-Box Polynomials Resultants. 201-204
Frédéric Roupin:
On Approximating the Memory-Constrained Module Allocation Problem. 205-208
Sung-Mo Park, Sangjin Lee, Soo Hak Sung, Kwangjo Kim:
Improving Bounds for the Number of Correlation Immune Boolean Functions. 209-212
Ying Choi, Tak Wah Lam:
Dynamic Suffix Tree and Two-Dimensional Texts Management. 213-220
Priyalal Kulasinghe:
Connectivity of the Crossed Cube. 221-226

Dimitrios M. Thilikos, Hans L. Bodlaender:
Fast Partitioning l-Apex Graphs with Application to Approximating Maximum Induced-Subgraph Problems. 227-232
Antoni W. Mazurkiewicz:
Distributed Enumeration. 233-239
Joseph M. Morris:
Non-Deterministic Expressions and Predicate Transformers. 241-246
Tiziana Calamoneri, Rossella Petreschi:
A New 3D Representation of Trivalent Cayley Networks. 247-252
Jean Frédéric Myoupo, Ahmad Wabbi:
Improved Linear Systolic Algorithms for Substring Statistics. 253-258
C. Micheneau:
Disjoint Hamiltonian Cycles in Recursive Circulant Graphs. 259-264
Kazuo Iwama, Chuzo Iwamoto, T. Ohsawa:
A Faster Parallel Algorithm for k-Connectivity. 265-269
Knut Verbarg:
Approximate Center Points in Dense Point Sets. 271-278
Berry Schoenmakers:
A Tight Lower Bound for Top-Down Skew Heaps. 279-284

Devendra Kumar, Abraham Silberschatz:
A Counter-Example to an Algorithm for the Generalized Input-Output Construct of CSP. 287
Eyal Kushilevitz:
A Simple Algorithm for Learning O (log n)-Term DNF. 289-292
Louis Ibarra:
Finding Pattern Matchings for Permutations. 293-295
Moshe Dror, Wieslaw Kubiak, Paolo Dell'Olmo:
Scheduling Chains to Minimize Mean Flow Time. 297-301
Nader H. Bshouty:
On Learning Multivariate Polynomials Under the Uniform Distribution. 303-309
H. S. Chao, Fang-Rong Hsu, Richard C. T. Lee:
An Optimal EREW Parallel Algorithm for Computing Breadth-First Search Trees on Permutation Graphs. 311-316
Jianer Chen, Saroja P. Kanchi, Arkady Kanevsky:
A Note on Approximating Graph Genus. 317-322
Athena Vakali, Yannis Manolopoulos:
An Exact Analysis on Expected Seeks in Shadowed Disks. 323-329
Paola Flocchini:
Minimal Sense of Direction in Regular Networks. 331-338

Last update Mon Feb 13 04:50:41 2012 CET by the DBLP Team —

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