default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDTheoretical Computer Science, Volume 410
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, Raphaël 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, John 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, Jorge 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
- Grzegorz Rozenberg:
Preface. 1413-1414 - Natasa Jonoska, Jarkko Kari:
Preface. 1415-1416 - Sam Greenberg, Dana Randall:
Convergence rates of Markov chains for some self-assembly and non-saturated Ising models. 1417-1427 - John H. Reif, Sudheer Sahu:
Autonomous programmable DNA nanorobotic devices using DNAzymes. 1428-1439 - N. E. Grayson, Anne Taormina, Reidun Twarock:
DNA duplex cage structures with icosahedral symmetry. 1440-1447 - Natasa Jonoska, Nadrian C. Seeman, Gang Wu:
On existence of reporter strands in DNA-based graph structures. 1448-1460 - Yuriy Brun, Dustin Reishus:
Path finding in the tile assembly model. 1461-1472
Volume 410, Number 16, April 2009
- Grzegorz Rozenberg:
Preface. 1473-1474 - Natasa Jonoska, Jarkko Kari:
Preface. 1475-1476 - Marcella Anselmo, Maria Madonia: