Volume 412, Numbers 1-2, January 2011
: A universal cellular automaton on the heptagrid of the hyperbolic plane with four states.
: Abstract geometrical computation 4: Small Turing universal signal machines.
: A simple P-complete problem and its language-theoretic representations.
Liesbeth De Mol
: On the complex behavior of simple tag systems - An experimental approach.
Jack H. Lutz
: A divergence formula for randomness and dimension.
Cristian S. Calude
: Simplicity via provability for universal prefix-free Turing machines.
: Computational processes, observers and Turing incompleteness.
Volume 412, Number 3, January 2011
, Guoliang Xue
: A linear time algorithm for computing a most reliable source on a tree network with faulty nodes.
, An Zhang
: Online hierarchical scheduling: An approach using mathematical programming.
, Xiwen Lu
: An improved approximation algorithm for single machine scheduling with job delivery.
Volume 412, Numbers 4-5, February 2011
, Guohui Lin
: The three column Bandpass problem is solvable in linear time.
, Fengshan Bai
: An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs.
: Speedup for natural problems and noncomputability.
Volume 412, Number 6, February 2011
Volume 412, Number 7, February 2011
Volume 412, Numbers 8-10, March 2011
, Chik How Tan
: Certificateless public key encryption: A new generic construction and two pairing-free schemes.
Jung Yeon Hwang
: A note on an identity-based ring signature scheme with signer verifiability.
: On average and highest number of flips in pancake sorting.
, Matthieu Latapy
: Post-processing hierarchical community structures: Quality improvements and multi-scale view.
: Approximating directed weighted-degree constrained networks.
: Construction of minimal deterministic finite automata from biological motifs.
Volume 412, Number 11, March 2011
Foto N. Afrati
: Determinacy and query rewriting for conjunctive queries and views.
: A short proof that adding some permutation rules to β preserves SN.
José Espírito Santo
: A note on preservation of strong normalisation in the λ-calculus.
Volume 412, Numbers 12-14, March 2011
, Uri Yovel
: Uniform unweighted set cover: The power of non-oblivious local search.
, Hairong Zhao
: Bicriteria scheduling concerned with makespan and total completion time subject to machine availability constraints.
, Liying Kang
: Online and semi-online hierarchical scheduling for load balancing on uniform machines.
: The transposition median problem is NP-complete.
: Recurrence and transience for finite probabilistic tables.
: Fast edge searching and fast searching on graphs.
Volume 412, Number 15, March 2011
, Raúl Marín
: Two discrete versions of the Inscribed Square Conjecture and some related problems.
, Jiu-Lun Fan
, Yin Zhu
: The optimal All-Partial-Sums algorithm in commutative semigroups and its applications for image thresholding segmentation.
Volume 412, Number 16, April 2011
Volume 412, Number 17, April 2011
Volume 412, Number 18, April 2011
, Jun Tarui
: A well-mixed function with circuit complexity 5n: Tightness of the Lachish-Raz-type bounds.
: On the OBDD complexity of the most significant bit of integer multiplication.
, Mia Minnes
: Deciding the isomorphism problem in classes of unary automatic structures.
: On the derandomization of the graph test for homomorphism over groups.
Volume 412, Number 19, April 2011
Volume 412, Number 20, April 2011
: Geometry of Interaction V: Logic in the hyperfinite factor.
: A linear algorithm for MLL proof net correctness and sequentialization.
: Intuitionistic differential nets and lambda-calculus.
Volume 412, Number 21, May 2011
Volume 412, Number 22, May 2011
, Moti Medina
: Parallel randomized load balancing: A lower bound for a more general model.
: Combined data structure for previous- and next-smaller-values.
Volume 412, Number 23, May 2011
Anke van Zuylen
: Linear programming based approximation algorithms for feedback set problems in bipartite tournaments.
Volume 412, Number 24, May 2011
: Proportional response dynamics in the Fisher market.
Volume 412, Number 25, June 2011
: Logical classification of distributed algorithms (Bakery algorithms as an example).
: Metric structures and probabilistic computation.
Volume 412, Number 26, June 2011
Volume 412, Number 27, June 2011
: A quick tour on suffix arrays and compressed suffix arrays.
: Last cases of Dejean's conjecture.
Volume 412, Number 28, June 2011
Dirk van Dalen
: Brouwer's ϵ-fixed point and Sperner's lemma.
: Probabilities, distribution monads, and convex categories.
Volume 412, Number 29, July 2011
Dong Han Kim
: Return time complexity of Sturmian sequences.
: Complexity of clique coloring and related problems.
: An improved lower bound on the sensitivity complexity of graph properties.
: Connectedness properties of dimension level sets.
: Special factors and the combinatorics of suffix and factor automata.
: Compositional synthesis of asynchronous automata.
: Inapproximability of maximal strip recovery.
: Fast minimal triangulation algorithm using minimum degree criterion.
Volume 412, Number 30, July 2011
: Generalized Besicovitch and Weyl spaces: Topology, patterns, and sliding block codes.
: Positive expansiveness versus network dimension in symbolic dynamical systems.
: Simulating reversible Turing machines and cyclic tag systems by one-dimensional reversible cellular automata.
Volume 412, Number 31, July 2011
Volume 412, Number 32, July 2011
: Approximation algorithms for variable voltage processors: Min energy, max throughput and online heuristics.
, Hisao Tamaki
: Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in O(n1+ϵ) time.
, Bin Fu
: Linear and sublinear time algorithms for the basis of abelian groups.
Volume 412, Number 33, July 2011