Volume 410,
Number 1,
January 2009
- Pinar Heggernes, Charis Papadopoulos:
Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions.
1-15
- Christian Choffrut, Serge Grigorieff:
Finite n-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al.
16-34
- Karol Suchan, Ioan Todinca:
Minimal interval completion through graph exploration.
35-43
- James D. Currie, Ali Aberkane:
A cyclic binary morphism avoiding Abelian fourth powers.
44-52
- Michael R. Fellows, Danny Hermelin, Frances A. Rosamond, Stéphane Vialette:
On the parameterized complexity of multiple-interval graph problems.
53-61
- Maryam Shoaran, Alex Thomo:
Fault-tolerant computation of distributed regular path queries.
62-77
- Ruifang Liu, Zhonghua Lu, Jinlong Shu:
The minimal Laplacian spectral radius of trees with a given diameter.
78-83
- Surender Baswana, Vishrut Goyal, Sandeep Sen:
All-pairs nearly 2-approximate shortest paths in I time.
84-93
- Satoshi Ikeda, Izumi Kubo, Masafumi Yamashita:
The hitting and cover times of random walks on finite graphs using local degree information.
94-100
- Piotr Faliszewski, Lane A. Hemaspaandra:
The complexity of power-index comparison.
101-107
- Tomás Masopust:
On the descriptional complexity of scattered context grammars.
108-112
Volume 410,
Numbers 2-3,
February 2009
- Marcello M. Bonsangue, Einar Broch Johnsen, Amy L. Murphy, Jan Vitek:
Preface.
113
- Philippe Bidinger, Adriana B. Compagnoni:
Pict correctness revisited.
114-127
- Frank S. de Boer:
A shared-variable concurrency analysis of multi-threaded object-oriented programs.
128-141
- Sara Capecchi, Mario Coppo, Mariangiola Dezani-Ciancaglini, Sophia Drossopoulou, Elena Giachino:
Amalgamating sessions and methods in object-oriented languages with generics.
142-167
- John Field, Maria-Cristina V. Marinescu, Christian Stefansen:
Reactors: A data-oriented synchronous/asynchronous programming model for distributed applications.
168-201
- Philipp Haller, Martin Odersky:
Scala Actors: Unifying thread-based and event-based programming.
202-220
- Jean-Marie Jacquet, Isabelle Linden:
Fully abstract models and refinements as tools to compare agents in timed coordination languages.
221-253
- Peter Csaba Ölveczky, Stian Thorvaldsen:
Formal modeling, performance estimation, and model checking of wireless sensor network algorithms in Real-Time Maude.
254-280
Volume 410,
Numbers 4-5,
February 2009
- Grzegorz Rozenberg:
Preface.
281-282
- Paola Bonizzoni, S. Barry Cooper, Benedikt Löwe, Andrea Sorbi:
Foreword.
283-284
- Claudio Zandron:
Nadia Busi (1968-2007).
285
- Nadia Busi, Claudio Zandron:
Computational expressiveness of Genetic Systems.
286-293
- Anne Condon, Hosna Jabbari:
Computational prediction of nucleic acid secondary structure: Methods, applications, and challenges.
294-301
- Ellie D'Hondt:
Quantum approaches to graph colouring.
302-309
- Andrzej Ehrenfeucht, Grzegorz Rozenberg:
Introducing time in reaction systems.
310-322
- Carmine Garzillo, Giuseppe Trautteur:
Computational virtuality in biological systems.
323-331
- Natasa Jonoska, Gregory L. McColm:
Complexity classes for self-assembling flexible tiles.
332-346
- Bjørn Kjos-Hanssen, Anil Nerode:
Effective dimension of points visited by Brownian motion.
347-354
- Shankara Narayanan Krishna:
Membrane computing with transport and embedded proteins.
355-375
- James Ladyman:
What does it mean to say that a physical system implements a computation?
376-383
- James I. Lathrop, Jack H. Lutz, Scott M. Summers:
Strict self-assembly of discrete Sierpinski triangles.
384-405
- Remco Loos, Florin Manea, Victor Mitrana:
On small, reduced, and fast universal accepting networks of splicing processors.
406-416
- Florin Manea, Victor Mitrana, Takashi Yokomori:
Two complementary operations inspired by the DNA hairpin formation: Completion and reduction.
417-425
- Philip D. Welch:
Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and Normal Form theorems.
426-442
- Damien Woods, Turlough Neary:
The complexity of small universal Turing machines: A survey.
443-450
Volume 410,
Numbers 6-7,
February 2009
- Ivan Lavallée, Alexander A. Shvartsman:
Editors' preface.
451-452
- Baruch Awerbuch, Christian Scheideler:
Robust random number generation for peer-to-peer systems.
453-466
- Rida A. Bazzi, Young-ri Choi, Mohamed G. Gouda:
Hop chains: Secure routing and the establishment of distinct identities.
467-480
- Jurek Czyzowicz, Leszek Gasieniec, Andrzej Pelc:
Gathering few fat mobile robots in the plane.
481-499
- Murat Demirbas, Anish Arora, Vinodkrishnan Kulathumani:
Glance: A lightweight querying service for wireless sensor networks.
500-513
- Shlomi Dolev, Nir Tzachar:
Empire of colonies: Self-stabilizing and self-organizing distributed algorithm.
514-532
- Burkhard Englert:
On the cost of uniform protocols whose memory consumption is adaptive to interval contention.
533-545
- Seth Gilbert, Rachid Guerraoui, Calvin C. Newport:
Of malicious motes and suspicious sensors: On the efficiency of malicious interference in wireless networks.
546-569
- Rachid Guerraoui, Maurice Herlihy, Bastian Pochon:
A topological treatment of early-deciding set-agreement.
570-580
- Colette Johnen, Le Huy Nguyen:
Robust self-stabilizing weight-based clustering algorithm.
581-594
- Marios Mavronicolas, Loizos Michael, Paul G. Spirakis:
Computing on a partially eponymous ring.
595-613
- Neeraj Mittal, Kuppahalli L. Phaneesh, Felix C. Freiling:
Safe termination detection in an asynchronous distributed system when processes may crash and recover.
614-628
- Heinrich Moser:
Towards a real-time distributed computing model.
629-659
Volume 410,
Numbers 8-10,
March 2009
- Deying Li, Hongwei Du, Peng-Jun Wan, Xiaofeng Gao, Zhao Zhang, Weili Wu:
Construction of strongly connected dominating sets in asymmetric multihop wireless networks.
661-669
- Marcos A. Kiwi, Mauricio Soto, Christopher Thraves:
Adversarial queuing theory with setups.
670-687
- Yong Gao:
The degree distribution of random k-trees.
688-695
- Selma Djelloul:
Treewidth and logical definability of graph products.
696-710
- Wolfgang W. Bein, Lawrence L. Larmore, Linda Morales, Ivan Hal Sudborough:
A quadratic time 2-approximation algorithm for block sorting.
711-717
- Jiong Guo:
A more effective linear kernelization for cluster editing.
718-726
- Yuchen Zhang, Xiaoming Sun:
The antimagicness of the Cartesian product of graphs.
727-735
- Willy Susilo:
Short fail-stop signature scheme based on factorization and discrete logarithm assumptions.
736-744
- Alexis C. Kaporis, Paul G. Spirakis:
The price of optimum in Stackelberg games on arbitrary single commodity networks and latency functions.
745-755
- Decheng Dai, Changyuan Yu:
A 5+epsilon-approximation algorithm for minimum weighted dominating set in unit disk graph.
756-765
- Ping-Ying Tsai, Jung-Sheng Fu, Gen-Huey Chen:
Fault-free longest paths in star networks with conditional link faults.
766-775
- C. T. Ng, Zhiyi Tan, Yong He, T. C. Edwin Cheng:
Two semi-online scheduling problems on two uniform machines.
776-792
- Francine Blanchet-Sadri, Robert Mercas, Geoffrey Scott:
A generalization of Thue freeness for partial words.
793-800
- Tzu-Liang Kung, Cheng-Kuan Lin, Tyne Liang, Lih-Hsing Hsu, Jimmy J. M. Tan:
On the bipanpositionable bipanconnectedness of hypercubes.
801-811
- Zhao Zhang, Xiaofeng Gao, Weili Wu:
Algorithms for connected set cover problem and fault-tolerant connected set cover problem.
812-817
- Jianer Chen, Iyad A. Kanj, Jie Meng, Ge Xia, Fenghui Zhang:
On the pseudo-achromatic number problem.
818-829
- Xianglai Qi, Shiguo Zhou, Jinjiang Yuan:
Single machine parallel-batch scheduling with deteriorating jobs.
830-836
- Aïda Ouangraoua, Pascal Ferraro:
A constrained edit distance algorithm between semi-ordered trees.
837-846
- Mathilde Bouvel, Dominique Rossin:
A variant of the tandem duplication - random loss model of genome rearrangement.
847-858
- Vera Asodi, Christopher Umans:
The complexity of the matroid-greedoid partition problem.
859-866
- Chi-Yuan Chan, Shan-Chyun Ku, Chi-Jen Lu, Biing-Feng Wang:
Efficient algorithms for two generalized 2-median problems and the group median problem on trees.
867-876
- Jianping Li, Weidong Li, Tongquan Zhang, Zhongxu Zhang:
The subdivision-constrained minimum spanning tree problem.
877-885
- Alessandro Ferrante, Gennaro Parlato, Francesco Sorrentino, Carmine Ventre:
Fast payment schemes for truthful mechanisms with verification.
886-899
- Wataru Matsubara, Shunsuke Inenaga, Akira Ishino, Ayumi Shinohara, Tomoyuki Nakamura, Kazuo Hashimoto:
Efficient algorithms to compute compressed longest common substrings and compressed palindromes.
900-913
- Hisashi Koga:
Dynamic TCP acknowledgment with sliding window.
914-925
- Sun-Yuan Hsieh, Chang-Jen Tu:
Constructing edge-disjoint spanning trees in locally twisted cubes.
926-932
- Spyros C. Kontogiannis, Paul G. Spirakis:
On the support size of stable strategies in random games.
933-942
- Vesa Halava, Tero Harju, Tomi Kärki, Patrice Séébold:
Overlap-freeness in infinite partial words.
943-948
- Jean Cardinal, Stefan Langerman, Eythan Levy:
Improved approximation bounds for edge dominating set in dense graphs.
949-957
- Travis Gagie:
Compressed depth sequences.
958-962
- Sung-Pil Hong, Myoung-Ju Park, Soo Y. Chang:
Approximation of the k-batch consolidation problem.
963-967
- Francine Blanchet-Sadri, Raphael M. Jungers, Justin Palumbo:
Testing avoidability on sets of partial words is hard.
968-972
- Pablo Sáez:
A quadratic algorithm for the 2-cyclic robotic scheduling problem.
973-976
- Yury L. Orlovich, Valery S. Gordon, Dominique de Werra:
On the inapproximability of independent domination in 2P3-free perfect graphs.
977-982
- Cinzia Pizzi:
k-difference matching in amortized linear time for all the words in a text.
983-987
- Tsung-Hsi Tsai:
Efficient computation of the iteration of functions.
988-993
- Martin Wahlen:
On the complexity of approximating the Hadwiger number.
994-996
- Juha Honkala:
On the simplification of infinite morphic words.
997-1000
Volume 410,
Number 11,
March 2009
- S. Barry Cooper, Hong Zhu:
Preface: Algorithms, complexity and models of computation.
1001-1002
- Vincent Danos, Linus J. Schumacher:
How liquid is biological signalling?
1003-1012
- Minming Li, Ze Feng, Nan Zang, Ronald L. Graham, Frances F. Yao:
Approximately optimal trees for group key management with batch updates.
1013-1021
- Wangsen Feng, Li'ang Zhang, Hanpin Wang:
Approximation algorithm for maximum edge coloring.
1022-1029
- Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk, Christian Schindelhauer:
Improving the average delay of sorting.
1030-1041
- Angsheng Li:
Elementary differences among jump classes.
1042-1053
- Hiroki Morizumi, Jun Tarui:
Linear-size log-depth negation-limited inverter for k-tonic binary sequences.
1054-1060
- Akifumi Kawaguchi, Hiroshi Nagamochi:
Drawing slicing graphs with face areas.
1061-1072
- He Sun, Chung Keung Poon:
Two improved range-efficient algorithms for F0 estimation.
1073-1080
- Yingchao Zhao, Shang-Hua Teng:
Combinatorial and spectral aspects of nearest neighbor graphs in doubling dimensional and nearly-Euclidean spaces.
1081-1092
- Peng Zhang, Mingji Xia:
An approximation algorithm to the k-Steiner Forest problem.
1093-1098
- Andrew Chi-Chih Yao, Frances F. Yao, Yunlei Zhao:
A note on universal composable zero-knowledge in the common reference string model.
1099-1108
Volume 410,
Numbers 12-13,
March 2009
- Andrei Popescu, Traian-Florin Serbanuta, Grigore Rosu:
A semantic approach to interpolation.
1109-1128
- H. Peter Gumm:
Copower functors.
1129-1142
- Simone Bova, Franco Montagna:
The consequence relation in the logic of commutative GBL-algebras is PSPACE-complete.
1143-1158
- Murdoch James Gabbay:
A study of substitution, using nominal techniques and Fraenkel-Mostowksi sets.
1159-1189
- Robert Lorenz, Gabriel Juhás, Robin Bergenthum, Jörg Desel, Sebastian Mauser:
Executability of scenarios in Petri nets.
1190-1216
- Lutz Schröder, Till Mossakowski:
HasCasl: Integrated higher-order specification and program development.
1217-1260
- Jan A. Bergstra, Yoram Hirshfeld, J. V. Tucker:
Meadows and the equational specification of division.
1261-1271
- Marta Z. Kwiatkowska, Gethin Norman, David Parker, Maria Grazia Vigliotti:
Probabilistic Mobile Ambients.
1272-1303
Volume 410,
Number 14,
March 2009
- Giuseppe Prencipe, Shmuel Zaks:
Preface.
1305-1306
- Nicolas Nisse, David Soguet:
Graph searching with advice.
1307-1318
- Hajo Broersma, Matthew Johnson, Daniël Paulusma:
Upper bounds and algorithms for parallel knock-out numbers.
1319-1327
- Eli Gafni, Achour Mostéfaoui, Michel Raynal, Corentin Travers:
From adaptive renaming to set agreement.
1328-1335
- Fredrik Manne, Morten Mjelde, Laurence Pilard, Sébastien Tixeuil:
A new self-stabilizing maximal matching algorithm.
1336-1345
- Peter Korteweg, Alberto Marchetti-Spaccamela, Leen Stougie, Andrea Vitaletti:
Data aggregation in sensor networks: Balancing communication and delay costs.
1346-1354
- Asaf Efrima, David Peleg:
Distributed algorithms for partitioning a swarm of autonomous mobile robots.
1355-1368
- Guy Even, Tamir Levi, Ami Litman:
Optimal conclusive sets for comparator networks.
1369-1376
- Rastislav Kralovic, Richard Královic:
Rapid almost-complete broadcasting in faulty networks.
1377-1387
- Jurek Czyzowicz, Stefan Dobrev, Evangelos Kranakis, Jaroslav Opatrny, Julià Urrutia:
Local edge colouring of Yao-like subgraphs of Unit Disk Graphs.
1388-1400
- Amos Korman, Shay Kutten:
A note on models for graph representations.
1401-1412
Volume 410,
Number 15,
April 2009
Volume 410,
Number 16,
April 2009
Volume 410,
Number 17,
April 2009
- Paul G. Spirakis, Marios Mavronicolas, Spyros C. Kontogiannis:
Preface.
1551
- Heiner Ackermann, Heiko Röglin, Berthold Vöcking:
Pure Nash equilibria in player-specific and weighted congestion games.
1552-1563
- Davide Bilò, Luciano Gualà, Guido Proietti:
Dynamic mechanism design.
1564-1572
- Xi Chen, Li-Sha Huang, Shang-Hua Teng:
Market equilibria with hybrid linear-Leontief utilities.
1573-1580
- Constantinos Daskalakis, Aranyak Mehta, Christos H. Papadimitriou:
A note on approximate Nash equilibria.
1581-1588
- Nicole Immorlica, Li (Erran) Li, Vahab S. Mirrokni, Andreas S. Schulz:
Coordination mechanisms for selfish scheduling.
1589-1598
- Spyros C. Kontogiannis, Panagiota N. Panagopoulou, Paul G. Spirakis:
Polynomial algorithms for approximating Nash equilibria of bimatrix games.
1599-1606
- Paolo Penna, Guido Proietti, Peter Widmayer:
Strongly polynomial-time truthful mechanisms in one shot.
1607-1615
Volume 410,
Number 18,
April 2009
- Lars Arge, Christian Cachin, Andrzej Tarlecki:
Preface.
1617
- Jin-yi Cai, Pinyan Lu:
Holographic algorithms: The power of dimensionality resolved.
1618-1628
- Benoit Larose, Pascal Tesson:
Universal algebra and hardness results for constraint satisfaction problems.
1629-1647
- Johannes Blömer, Stefanie Naewe:
Sampling methods for shortest vectors, closest vectors and successive minima.
1648-1665
- Albert Atserias, Andrei A. Bulatov, Anuj Dawar:
Affine systems of equations and counting infinitary logic.
1666-1683
- Manuel Bodirsky, Hubie Chen, Jan Kára, Timo von Oertzen:
Maximal infinite-valued constraint languages.
1684-1693
- Bernard Boigelot, Julien Brusten:
A generalization of Cobham's theorem to automata over real numbers.
1694-1703
- Marcelo P. Fiore, Chung-Kil Hur:
On the construction of free algebras for equational systems.
1704-1729
- Yuval Ishai, Tal Malkin, Martin J. Strauss, Rebecca N. Wright:
Private multiparty sampling and approximation of vector combinations.
1730-1745
Volume 410,
Number 19,
April 2009
- Marcus Hutter, Rocco A. Servedio:
Preface.
1747-1748
- Markus Maier, Matthias Hein, Ulrike von Luxburg:
Optimal construction of k-nearest-neighbor graphs for identifying noisy clusters.
1749-1764
- Kevin L. Chang:
Multiple pass streaming algorithms for learning mixtures of distributions in Rd.
1765-1780
- Vladimir V. V'yugin:
On calibration error of randomized forecasting algorithms.
1781-1795
- Sanjay Jain, Frank Stephan, Nan Ye:
Prescribed learning of r.e. classes.
1796-1806
- Ryo Yoshinaka:
Learning efficiency of very simple grammars from positive data.
1807-1825
- M. M. Hassan Mahmud:
On universal transfer learning.
1826-1846
- Kilho Shin, Tetsuji Kuboyama:
Polynomial summaries of positive semidefinite kernels.
1847-1862
- John Case, Samuel E. Moelius:
Parallelism increases iterative learning power.
1863-1875
- Jean-Yves Audibert, Rémi Munos, Csaba Szepesvári:
Exploration-exploitation tradeoff using variance estimates in multi-armed bandits.
1876-1902
- Vitaly Feldman, Shrenik Shah:
Separating models of learning with faulty teachers.
1903-1912
Volume 410,
Number 20,
May 2009
Volume 410,
Numbers 21-23,
May 2009
- Alexander Meduna, Jirí Techet:
An infinite hierarchy of language families generated by scattered context grammars with n-limited derivations.
1961-1969
- Pierre Fraigniaud, Cyril Gavoille, Adrian Kosowski, Emmanuelle Lebhar, Zvi Lotker:
Universal augmentation schemes for network navigability.
1970-1981
- Guanghui Wang, Guizhen Liu:
Paths, cycles and circular colorings in digraphs.
1982-1985
- Marcus Oswald, Gerhard Reinelt:
The simultaneous consecutive ones problem.
1986-1992
- Isaac Elias, Jens Lagergren:
Fast neighbor joining.
1993-2000
- Jinn-Shyong Yang, Jou-Ming Chang, Shyue-Ming Tang, Yue-Li Wang:
On the independent spanning trees of recursive circulant graphs G(cdm, d) with d>2.
2001-2010
- Christian Glaßer, Alan L. Selman, Stephen D. Travers, Liyu Zhang:
Non-mitotic sets.
2011-2023
- Wenbin Chen, Matthew C. Schmidt, Nagiza F. Samatova:
On parameterized complexity of the Multi-MCS problem.
2024-2032
- Adrien Guignard, Eric Sopena:
Compound Node-Kayles on paths.
2033-2044
- Herbert Fleischner, Egbert Mujuni, Daniël Paulusma, Stefan Szeider:
Covering graphs with few complete bipartite subgraphs.
2045-2053
- Stefan S. Dantchev, Barnaby Martin, Mark Rhodes:
Tight rank lower bounds for the Sherali-Adams proof system.
2054-2063
- Takayuki Nagoya, Seinosuke Toda:
Computational complexity of computing a partial solution for the Graph Automorphism problems.
2064-2071
- Liliana Alcón, Luerbio Faria, Celina M. Herrera de Figueiredo, Marisa Gutierrez:
The complexity of clique graph recognition.
2072-2083
- Ilya Goldstein:
Asymptotic subword complexity of fixed points of group substitutions.
2084-2098
- Ming Liu, Yinfeng Xu, Chengbin Chu, Feifeng Zheng:
Online scheduling on two uniform machines to minimize the makespan.
2099-2109
- Roberto Baldoni, Silvia Bonomi,
