Information Processing Letters, Volume 99

Volume 99, Number 1, July 2006

Huaming Zhang, Xin He:
On simultaneous straight-line grid embedding of a planar graph and its dual. 1-6
Electronic Edition (link) BibTeX
Robert E. Jamison, Gretchen L. Matthews, John Villalpando:
Acyclic colorings of products of trees. 7-12
Electronic Edition (link) BibTeX
Mitre Costa Dourado, Fábio Protti, Jayme Luiz Szwarcfiter:
Complexity aspects of generalized Helly hypergraphs. 13-18
Electronic Edition (link) BibTeX
Yangjun Chen:
On the cost of searching signature trees. 19-26
Electronic Edition (link) BibTeX
Christian Choffrut, Serge Grigorieff:
Separability of rational relations in A* × N^m by recognizable relations is decidable. 27-32
Electronic Edition (link) BibTeX
Anca Muscholl, Mathias Samuelides, Luc Segoufin:
Complementing deterministic tree-walking automata. 33-39
Electronic Edition (link) BibTeX

Angelika Hellwig, Lutz Volkmann:
Lower bounds on the vertex-connectivity of digraphs and graphs. 41-46
Electronic Edition (link) BibTeX
Min Chen, Weifan Wang:
The 2-dipath chromatic number of Halin graphs. 47-53
Electronic Edition (link) BibTeX
Amitabha Bagchi, Ankur Bhargava, Torsten Suel:
Approximate maximum weight branchings. 54-58
Electronic Edition (link) BibTeX
Kathie Cameron, Chính T. Hoàng:
On the structure of certain intersection graphs. 59-63
Electronic Edition (link) BibTeX
Chung-Ming Lin, Yin-Te Tsai, Chuan Yi Tang:
Balancing minimum spanning trees and multiple-source minimum routing cost spanning trees on metric graphs. 64-67
Electronic Edition (link) BibTeX
Mickaël Montassier:
A note on the not 3-choosability of some families of planar graphs. 68-71
Electronic Edition (link) BibTeX
Olga Xirotiri:
Simulation of simultaneous safe recursion over an arbitrary structure. 72-81
Electronic Edition (link) BibTeX

Konstantinos Bletsas, Neil C. Audsley:
Optimal priority assignment in the presence of blocking. 83-86
Electronic Edition (link) BibTeX
Adi Avidor, Ricky Rosen:
A note on Unique Games. 87-91
Electronic Edition (link) BibTeX
Marcin Peczarski:
An improvement of the tree code construction. 92-95
Electronic Edition (link) BibTeX
Seth Voorhies, Hyunyoung Lee, Andreas Klappenecker:
Fair service for mice in the presence of elephants. 96-101
Electronic Edition (link) BibTeX
T. C. Edwin Cheng, C. T. Ng, Vladimir Kotov:
A new algorithm for online uniform-machine scheduling to minimize the makespan. 102-105
Electronic Edition (link) BibTeX
Shih-Chien Chou, Yuan-Chien Chen:
Retrieving reusable components with variation points from software product lines. 106-110
Electronic Edition (link) BibTeX
Sándor Vágvölgyi:
Descendants of a recognizable tree language for sets of linear monadic term rewrite rules. 111-118
Electronic Edition (link) BibTeX
Stefan Hougardy, Doratha E. Drake Vinkemeier:
Approximating weighted matchings in parallel. 119-123
Electronic Edition (link) BibTeX

Minghui Jiang:
A new approximation algorithm for labeling points with circle pairs. 125-129
Electronic Edition (link) BibTeX
Raphael Yuster:
Finding and counting cliques and independent sets in r-uniform hypergraphs. 130-134
Electronic Edition (link) BibTeX
Chik How Tan:
Analysis of improved signcryption scheme with key privacy. 135-138
Electronic Edition (link) BibTeX
Guangjun Xu, Liying Kang, Erfang Shan:
Acyclic domination on bipartite permutation graphs. 139-144
Electronic Edition (link) BibTeX
Boaz Tsaban:
Fast generators for the Diffie-Hellman key agreement protocol and malicious standards. 145-148
Electronic Edition (link) BibTeX
Wei Huang, Yaoyun Shi, Shengyu Zhang, Yufan Zhu:
The communication complexity of the Hamming distance problem. 149-153
Electronic Edition (link) BibTeX
Marten van Dijk, Tom A. M. Kevenaar, Geert Jan Schrijen, Pim Tuyls:
Improved constructions of secret sharing schemes by applying (lambda, omega)-decompositions. 154-157
Electronic Edition (link) BibTeX
Olivier Danvy, Henning Korsholm Rohde:
On obtaining the Boyer-Moore string-matching algorithm by partial evaluation. 158-162
Electronic Edition (link) BibTeX
Satoshi Ikeda, Koji Nakazawa:
Strong normalization proofs by CPS-translations. 163-170
Electronic Edition (link) BibTeX

Yasuhiko Takenaga, Toby Walsh:
Tetravex is NP-complete. 171-174
Electronic Edition (link) BibTeX
Alistair Moffat, Vo Ngoc Anh:
Binary codes for locally homogeneous sequences. 175-180
Electronic Edition (link) BibTeX
Markus Kuba:
On Quickselect, partial sorting and Multiple Quickselect. 181-186
Electronic Edition (link) BibTeX
Asaf Levin:
Real time scheduling with a budget: Parametric-search is better than binary search. 187-191
Electronic Edition (link) BibTeX
Shisheng Li, Guangzhong Sun, Guoliang Chen:
Improved algorithm for finding next-to-shortest paths. 192-194
Electronic Edition (link) BibTeX
Julián Mestre:
On the multi-radius cover problem. 195-198
Electronic Edition (link) BibTeX
Philippe Janssen, Lhouari Nourine:
Minimum implicational basis for meet-semidistributive lattices. 199-202
Electronic Edition (link) BibTeX
Yoshifumi Sakai:
A linear space algorithm for computing a longest common increasing subsequence. 203-207
Electronic Edition (link) BibTeX
Raymond R. Devillers, Laurent Van Begin:
Boundedness undecidability for synchronized nets. 208-214
Electronic Edition (link) BibTeX

André Große, Jörg Rothe, Gerd Wechsung:
On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P. 215-221
Electronic Edition (link) BibTeX
Stavros Tripakis:
Folk theorems on the determinization and minimization of timed automata. 222-226
Electronic Edition (link) BibTeX
C. R. Subramanian:
Analysis of a heuristic for acyclic edge colouring. 227-229
Electronic Edition (link) BibTeX
Adrian Kosowski, Michal Malafiejski, Pawel Zylinski:
An approximation algorithm for maximum P₃-packing in subcubic graphs. 230-233
Electronic Edition (link) BibTeX
Amin Coja-Oghlan, Lars Kuhtz:
An improved algorithm for approximating the chromatic number of G_{n, p}. 234-238
Electronic Edition (link) BibTeX
Felix A. Fischer, Markus Holzer, Stefan Katzenbeisser:
The influence of neighbourhood and choice on the complexity of finding pure Nash equilibria. 239-245
Electronic Edition (link) BibTeX
Travis Gagie:
Large alphabets and incompressibility. 246-251
Electronic Edition (link) BibTeX