Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDTheoretical Computer Science, Volume 412
Volume 412, Numbers 1-2, January 2011
- Damien Woods
, Turlough Neary, Anthony Karel Seda:
Preface. 1 - Eric Goles Ch., Pierre-Etienne Meunier, Ivan Rapaport, Guillaume Theyssier:
Communication complexity and intrinsic universality in cellular automata. 2-21 - Nicolas Ollinger, Gaétan Richard:
Four states are enough! 22-32 - Maurice Margenstern:
A universal cellular automaton on the heptagrid of the hyperbolic plane with four states. 33-56 - Jérôme Durand-Lose:
Abstract geometrical computation 4: Small Turing universal signal machines. 57-67 - Alexander Okhotin:
A simple P-complete problem and its language-theoretic representations. 68-82 - Markus Holzer, Martin Kutrib, Andreas Malcher:
Complexity of multi-head finite automata: Origins and directions. 83-96 - Liesbeth De Mol:
On the complex behavior of simple tag systems - An experimental approach. 97-112 - Matteo Cavaliere, Peter Leupold:
Computing by observing: Simple systems and simple observers. 113-123 - Erzsébet Csuhaj-Varjú, Sergey Verlan:
On generalized communicating P systems with minimal interaction rules. 124-135 - Artiom Alhazov, Alexander Krassovitskiy, Yurii Rogozhin, Sergey Verlan:
P systems with minimal insertion and deletion. 136-144 - David Doty, Matthew J. Patitz, Scott M. Summers:
Limitations of self-assembly at temperature 1. 145-158 - Matthew J. Patitz, Scott M. Summers:
Self-assembly of infinite structures: A survey. 159-165 - Jack H. Lutz:
A divergence formula for randomness and dimension. 166-177 - Cristian S. Calude:
Simplicity via provability for universal prefix-free Turing machines. 178-182 - Klaus Sutner:
Computational processes, observers and Turing incompleteness. 183-190
Volume 412, Number 3, January 2011
- Ding-Zhu Du, Xiaodong Hu, Panos M. Pardalos:
Preface. 191
- Yinfeng Xu, Wenming Zhang, Feifeng Zheng:
Optimal algorithms for the online time series search problem. 192-197 - Feng Zou, Yuexuan Wang, XiaoHua Xu, Xianyue Li, Hongwei Du, Peng-Jun Wan, Weili Wu:
New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs. 198-208 - Deying Li, Yuexuan Wang, Qinghua Zhu, Huiqiang Yang:
Fault-tolerant routing: k-inconnected many-to-one routing in wireless networks. 209-216 - Suogang Gao, Zengti Li, Jiangchen Yu, Xiaofeng Gao, Weili Wu:
DNA library screening, pooling design and unitary spaces. 217-224 - Wei Ding, Guoliang Xue:
A linear time algorithm for computing a most reliable source on a tree network with faulty nodes. 225-232 - Deshi Ye, Xin Han, Guochuan Zhang:
Online multiple-strip packing. 233-239 - Zhipeng Cai, Randy Goebel, Guohui Lin:
Size-constrained tree partitioning: Approximating the multicast k-tree routing problem. 240-245 - Zhiyi Tan, An Zhang:
Online hierarchical scheduling: An approach using mathematical programming. 246-256 - Eduardo Álvarez-Miranda, Xujin Chen, Jie Hu, Xiaodong Hu, Alfredo Candia-Véjar:
Deterministic risk control for cost-effective network connections. 257-264 - Feng Wang, David Hongwei Du, Erika Camacho, Kuai Xu, Wonjun Lee, Yan Shi, Shan Shan:
On positive influence dominating sets in social networks. 265-269 - Peihai Liu, Xiwen Lu:
An improved approximation algorithm for single machine scheduling with job delivery. 270-274
Volume 412, Numbers 4-5, February 2011
- Baoqiang Fan, Shisheng Li, Li Zhou, Liqi Zhang:
Scheduling resumable deteriorating jobs on a single machine with non-availability constraints. 275-280 - Zhong Li, Guohui Lin:
The three column Bandpass problem is solvable in linear time. 281-299 - Tullio Ceccherini-Silberstein, Michel Coornaert:
On the reversibility and the closed image property of linear cellular automata. 300-306 - Ryotaro Okazaki, Hirotaka Ono, Taizo Sadahiro, Masafumi Yamashita:
Broadcastings and digit tilings on three-dimensional torus networks. 307-319 - Paola Alimonti, Esteban Feuerstein, Luigi Laura, Umberto Nanni:
Linear time analysis of properties of conflict-free and general Petri nets. 320-338 - Li-Jui Chen, Jinn-Jy Lin, Min-Zheng Shieh, Shi-Chun Tsai:
More on the Magnus-Derek game. 339-344 - Clemens Thielen, Stephan Westphal:
Complexity of the traveling tournament problem. 345-351 - Tatsuya Akutsu, Daiji Fukagawa, Atsuhiro Takasu, Takeyuki Tamura:
Exact algorithms for computing the tree edit distance between unordered trees. 352-364 - Adam Kasperski, Pawel Zielinski:
On the approximability of robust spanning tree problems. 365-374 - Christian Knauer, Klaus Kriegel, Fabian Stehn:
Minimizing the weighted directed Hausdorff distance between colored point sets under translations and rigid motions. 375-382 - Hiroshi Nagamochi:
Cop-robber guarding game with cycle robber-region. 383-390 - Franz-Josef Brandenburg, Mao-cheng Cai:
Shortest path and maximum flow problems in networks with additive losses and gains. 391-401 - Geneviève Paquin, Christophe Reutenauer:
On the superimposition of Christoffel words. 402-418 - Jinshan Zhang, Fengshan Bai:
An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs. 419-429 - Chun-Cheng Lin, Hsu-Chun Yen, Sheung-Hung Poon, Jia-Hao Fan:
Complexity analysis of balloon drawing for rooted trees. 430-447 - Warren D. Nichols, Robert G. Underwood:
Algebraic Myhill-Nerode Theorems. 448-457 - Dana Pardubská, Martin Plátek, Friedrich Otto:
Parallel communicating grammar systems with regular control and skeleton preserving FRR automata. 458-477 - Hunter Monroe:
Speedup for natural problems and noncomputability. 478-481 - Mikhail Andreev, Ilya P. Razenshteyn, Alexander Shen:
Not every domain of a plain decompressor contains the domain of a prefix-free one. 482-486 - Amir M. Ben-Amram, Simon Yoffe:
A simple and efficient Union-Find-Delete algorithm. 487-492 - Srecko Brlek, Christophe Reutenauer:
Complexity and palindromic defect of infinite words. 493-497
Volume 412, Number 6, February 2011
- Grzegorz Rozenberg:
Preface. 499 - Jon Timmis, Paul S. Andrews, Andrew Hone:
Preface. 500-501
- Chris McEwan, Emma Hart:
On clonal selection. 502-516 - Thomas Jansen, Christine Zarges:
Analyzing different variants of immune inspired somatic contiguous hypermutations. 517-533 - Michael Elberfeld, Johannes Textor:
Negative selection algorithms on strings with efficient training and linear-time classification. 534-542 - Thomas Jansen, Christine Zarges:
On benefits and drawbacks of aging strategies for randomized search heuristics. 543-559
Volume 412, Number 7, February 2011
- Christos Kaklamanis, Martin Skutella:
Preface. 561-562
- Wolfgang W. Bein, Kazuo Iwama, Jun Kawahara, Lawrence L. Larmore, James A. Oravec:
A randomized algorithm for two servers in cross polytope spaces. 563-572 - Amitai Armon:
On min-max r-gatherings. 573-582 - Johann L. Hurink, Jacob Jan Paulus:
Improved online algorithms for parallel job scheduling and strip packing. 583-593 - Marek Chrobak, Mathilde Hurand:
Better bounds for incremental medians. 594-601 - Robert Krauthgamer, Aranyak Mehta, Atri Rudra:
Pricing commodities. 602-613 - Nedialko B. Dimitrov, C. Greg Plaxton:
Buyer-supplier games: Optimization over the core. 614-625 - Iftah Gamzu:
Improved lower bounds for non-utilitarian truthfulness. 626-632
Volume 412, Numbers 8-10, March 2011
- Vincenzo Bonifaci, Peter Korteweg, Alberto Marchetti-Spaccamela, Leen Stougie:
The distributed wireless gathering problem. 633-641 - György Dósa, Yuxin Wang, Xin Han, He Guo:
Online scheduling with rearrangement on two related machines. 642-653 - Robert D. Gray, António Malheiro:
Finite complete rewriting systems for regular semigroups. 654-661 - Guomin Yang, Chik How Tan:
Certificateless public key encryption: A new generic construction and two pairing-free schemes. 662-674 - Felix Brandt, Felix A. Fischer, Markus Holzer:
Equilibria of graphical games with symmetries. 675-685 - Sun-Yuan Hsieh:
On parallel recognition of cographs. 686-694 - Anthony Labarre, Josef Cibulka:
Polynomial-time sortable stacks of burnt pancakes. 695-702 - Heather Betel, Paola Flocchini:
On the relationship between fuzzy and Boolean cellular automata. 703-713 - Bo Cui, Lila Kari, Shinnosuke Seki:
Block insertion and deletion on trajectories. 714-728 - Urban Larsson, Peter Hegarty, Aviezri S. Fraenkel:
Invariant and dual subtraction games resolving the Duchêne-Rigo conjecture. 729-735 - Zoltán Fülöp, Magnus Steinby:
Varieties of recognizable tree series over fields. 736-752 - Aïda Ouangraoua, Valentin Guignon, Sylvie Hamel, Cédric Chauve:
A new algorithm for aligning nested arc-annotated sequences under arbitrary weight schemes. 753-764 - Martin Beaudry, Markus Holzer:
On the size of inverse semigroups given by generators. 765-772 - Kei Uchizawa, Eiji Takimoto, Takao Nishizeki:
Size-energy tradeoffs for unate circuits computing symmetric Boolean functions. 773-782 - Yotam Elor, Alfred M. Bruckstein:
Uniform multi-agent deployment on a ring. 783-795 - Jung Yeon Hwang:
A note on an identity-based ring signature scheme with signer verifiability. 796-804 - Zoltán Ésik, Szabolcs Iván:
Büchi context-free languages. 805-821 - Josef Cibulka:
On average and highest number of flips in pancake sorting. 822-834 - Zuzana Masáková, Edita Pelantová, Tomás Vávra:
Arithmetics in number systems with a negative base. 835-845 - Feodor F. Dragan, Fedor V. Fomin, Petr A. Golovach:
Approximation of minimum weight spanners for sparse graphs. 846-852 - Christian Glaßer, Christian Reitwießner, Victor L. Selivanov:
The shrinking property for NP and coNP. 853-864 - Zhongzhi Zhang, Francesc Comellas:
Farey graphs as models for complex networks. 865-875 - Wai-Fong Chuan, Chun-Yu Chen, Hui-Ling Ho, Fang-Yi Liao:
α-words and the radix order. 876-891 - Pascal Pons, Matthieu Latapy:
Post-processing hierarchical community structures: Quality improvements and multi-scale view. 892-900 - Zeev Nutov:
Approximating directed weighted-degree constrained networks. 901-912 - Weifan Wang, Xubin Yue, Xuding Zhu:
The surviving rate of an outerplanar graph for the firefighter problem. 913-921 - Tobias Marschall:
Construction of minimal deterministic finite automata from biological motifs. 922-930
Volume 412, Number 11, March 2011
- Joaquín Aguado, Michael Mendler:
Constructive semantics for instantaneous reactions. 931-961 - César Domínguez, Julio Rubio:
Effective homology of bicomplexes, formalized in Coq. 962-970 - Giorgi Japaridze:
Toggling operators in computability logic. 971-1004 - Foto N. Afrati:
Determinacy and query rewriting for conjunctive queries and views. 1005-1021
- René David:
A short proof that adding some permutation rules to β preserves SN. 1022-1026 - José Espírito Santo:
A note on preservation of strong normalisation in the λ-calculus. 1027-1032
Volume 412, Numbers 12-14, March 2011
- Asaf Levin, Uri Yovel:
Uniform unweighted set cover: The power of non-oblivious local search. 1033-1053 - Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, Yushi Uno:
On the complexity of reconfiguration problems. 1054-1065 - Roberto Baldoni, Antonio Fernández Anta, Kleoni Ioannidou, Alessia Milani:
The impact of mobility on the geocasting problem in mobile ad-hoc networks: Solvability and cost. 1066-1080 - Yumei Huo, Hairong Zhao:
Bicriteria scheduling concerned with makespan and total completion time subject to machine availability constraints. 1081-1091 - Li-ying Hou, Liying Kang:
Online and semi-online hierarchical scheduling for load balancing on uniform machines. 1092-1098 - Martin Bader:
The transposition median problem is NP-complete. 1099-1110 - Stepán Starosta:
On theta-palindromic richness. 1111-1121 - Weiwei Wu, Minming Li, Enhong Chen:
Min-energy scheduling for aligned jobs in accelerate model. 1122-1139 - Manfred Droste, Karin Quaas:
A Kleene-Schützenberger theorem for weighted timed automata. 1140-1153 - Mathieu Tracol:
Recurrence and transience for finite probabilistic tables. 1154-1168 - Vassilis Kountouriotis, Christos Nomikos, Panos Rondogiannis:
A game-theoretic characterization of Boolean grammars. 1169-1183 - Sebastian Böcker, Quang Bao Anh Bui, Anke Truß:
Computing bond orders in molecule graphs. 1184-1195 - Oren Ben-Zwi, Amir Ronen:
Local and global price of anarchy of graphical games. 1196-1207 - Boting Yang:
Fast edge searching and fast searching on graphs. 1208-1219 - Benoît Libert, Moti Yung:
Efficient traceable signatures in the standard model. 1220-1242 - Hagit Attiya, Eshcar Hillel:
Highly concurrent multi-word synchronization. 1243-1262 - Telikepalli Kavitha, Meghana Nasre:
Popular matchings with variable item copies. 1263-1274 - Pinar Heggernes, Daniel Meister, Andrzej Proskurowski:
Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs. 1275-1297
Volume 412, Number 15, March 2011
- Valentin E. Brimkov, Reneta P. Barneva, Petra Wiederhold:
Preface. 1299-1300
- Feliu Sagols, Raúl Marín:
Two discrete versions of the Inscribed Square Conjecture and some related problems. 1301-1312 - Valentin E. Brimkov, Andrew Leach, Michael Mastroianni, Jimmy Wu:
Guarding a set of line segments in the plane. 1313-1324 - Alexandre Borghi, Jérôme Darbon, Sylvain Peyronnet:
Exact optimization for the ℓ1-Compressive Sensing problem using a modified Dantzig-Wolfe method. 1325-1337 - Filip Malmberg, Joakim Lindblad, Natasa Sladoje, Ingela Nyström:
A graph-based framework for sub-pixel image segmentation. 1338-1349 - Robin Strand, Benedek Nagy, Gunilla Borgefors:
Digital distance functions on three-dimensional grids. 1350-1363 - Benedek Nagy, Robin Strand:
Approximating Euclidean circles by neighbourhood sequences in a hexagonal grid. 1364-1377 - Yohan Thibault, Akihiro Sugimoto, Yukiko Kenmochi:
3D discrete rotations using hinge angles. 1378-1391 - Stéphane Gosselin, Guillaume Damiand, Christine Solnon:
Efficient search of combinatorial maps using signatures. 1392-1405 - Phuc Quang Le, Abdullah M. Iliyasu, Fangyan Dong, Kaoru Hirota:
Strategies for designing geometric transformations on quantum images. 1406-1418 - Xie Xie, Jiu-Lun Fan, Yin Zhu:
The optimal All-Partial-Sums algorithm in commutative semigroups and its applications for image thresholding segmentation. 1419-1433 - Oscar Dalmau Cedeño, Mariano Rivera:
Alpha Markov Measure Field model for probabilistic image segmentation. 1434-1441
Volume 412, Number 16, April 2011
- Ilias S. Kotsireas, Bernard Mourrain, Victor Y. Pan:
Preface. 1443-1444
- Annie A. M. Cuyt, Wen-shin Lee:
Sparse interpolation of multivariate rational functions. 1445-1456