Volume 109, Number 1, December 2008
, Asaf Levin
: Asymptotic fully polynomial approximation schemes for variants of open-end bin packing.
: A note on the size of OBDDs for the graph of integer multiplication.
: Online uniformity of integer points on a line.
Volume 109, Number 2, December 2008
: A general mixing strategy for the ECB-Mix-ECB mode of operation.
: A note on the distribution of the number of prime factors of the integers.
: Stability bounds in networks with dynamic link capacities.
Volume 109, Number 3, January 2009
: On some open problems in reflective inductive inference.
Volume 109, Number 4, January 2009
: There are no pure relational width 2 constraint satisfaction problems.
: Using the incompressibility method to obtain local lemma results for Ramsey-type problems.
Volume 109, Number 5, February 2009
: A note on I-completeness of NP-witnessing relations.
, Carlos S. Subi
: Nearly tight bounds on the number of Hamiltonian circuits of the hypercube and generalizations.
: A nondeterministic space-time tradeoff for linear codes.
Volume 109, Number 6, February 2009
Volume 109, Number 7, March 2009
Gerhard J. Woeginger
: A comment on parallel-machine scheduling under a grade of service provision to minimize makespan.
, Xiwen Lu
: Preemptive stochastic online scheduling on two uniform machines.
Volume 109, Number 8, March 2009
: Some results on topological properties of folded hypercubes.
, Qian-Ping Gu
: 1.5-Approximation algorithm for weighted maximum routing and wavelength assignment on rings.
: New differential approximation algorithm for k-customer vehicle routing problem.
Volume 109, Number 9, April 2009
: Maximum vertex occupation time and inert fugitive: Recontamination does help.
: An analytical upper bound on the minimum number of recombinations in the history of SNP sequences in populations.
: Connectivity in a random interval graph with access points.
Volume 109, Number 10, April 2009
: Universal hash functions for an infinite universe and hash trees.
, Wenhui Zhang
: A direct construction of polynomial-size OBDD proof of pigeon hole problem.
: An elementary proof of a generalization of double Greibach normal form.
: On the size of (generalized) OBDDs for threshold functions.
Balder ten Cate
: A note on the expressibility problem for modal logics and star-free regular expressions.
Volume 109, Number 11, May 2009
, Dawu Gu
: Fully CCA2 secure identity based broadcast encryption without random oracles.
Milan R. Rapaic
, Zeljko Kanovic
: Time-varying PSO - convergence analysis, convergence-related parameterization and new parameter adjustment schemes.
: An aggressive algorithm for multiple string matching.
: A polynomial algorithm for the multiple knapsack problem with divisible item sizes.
Volume 109, Number 12, May 2009
: Common knowledge does not have the Beth property.
: An algorithm for solving the longest increasing circular subsequence problem.
Volume 109, Number 13, June 2009
: A pseudo-random network mobile automaton with linear growth.
Michael T. Goodrich
: On the algorithmic complexity of the Mastermind game with black-peg results.
: Efficient generation of the ideals of a poset in Gray code order.
: Optimized random number generation in an interval.
: A note on predecessor searching in the pointer machine model.
: Linear kernelizations for restricted 3-Hitting Set problems.
Volume 109, Number 14, June 2009
, Bernd Hauck
: A self-stabilizing algorithm for constructing weakly connected minimal dominating sets.
: More restrictive Gray codes for some classes of pattern avoiding permutations.
, R. Wei
: Comments on "Distributed symmetric key management for mobile ad hoc networks".
Volume 109, Number 15, July 2009
, Jianguo Qian
: On f-fault tolerant arc-forwarding and optical indices of all-optical folded hypercubes.
, Xiaofeng Chen
: Cryptanalysis and improvement of an ID-based ad-hoc anonymous identification scheme at CT-RSA 05.
: EXPSPACE lower bounds for the simulation preorder between a communication-free Petri net and a finite-state system.
, Ing-Ray Chen
: Elastic threshold-based admission control for QoS satisfaction with reward optimization for servicing multiple priority classes in wireless networks.
: An O(log(n)/log(log(n))) upper bound on the price of stability for undirected Shapley network design games.
Volume 109, Number 16, July 2009
: On some open problems in monotonic and conservative learning.
, Ryan Flynn
: The average number of block interchanges needed to sort a permutation and a recent result of Stanley.
, Klara Kedem
: Geometric pattern matching for point sets in the plane under similarity transformations.
: Assembling approximately optimal binary search trees efficiently using arithmetics.
Volume 109, Number 17, August 2009
Bang Ye Wu
: An optimal algorithm for the maximum-density path in a tree.
, Wei Chen
: Bounded cost algorithms for multivalued consensus using binary consensus instances.
Volume 109, Number 18, August 2009
: A simplified way of proving trade-off results for resolution.
B. S. Panda
, Sajal K. Das
: A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs.
: Computing the subset partial order for dense families of sets.
: A simple algorithm to find Hamiltonian cycles in proper interval graphs.
Volume 109, Number 19, September 2009
: New instability results for high-dimensional nearest neighbor search.
: A note on Rooted Survivable Networks.
, Hongyi Yao
: Seed optimization for i.i.d. similarities is no easier than optimal Golomb ruler design.
: A note on path bipancyclicity of hypercubes.
Volume 109, Number 20, September 2009
: Security of self-certified signatures.
, Zhao Zhang
: Vertex fault tolerance of optimal-kappa graphs and super-kappa graphs.
, Igor Razgon
: Constant ratio fixed-parameter approximation of the edge multicut problem.
: On the complexity of signed and minus total domination in graphs.
Volume 109, Numbers 21-22, October 2009
: Edge-fault-tolerant node-pancyclicity of twisted cubes.
Volume 109, Numbers 23-24, November 2009
: k-Fold unions of low-dimensional concept classes.