


Остановите войну!
for scientists:


default search action
Theoretical 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 - Philippe P. Pébay
, J. Maurice Rojas, David C. Thompson
:
Optimizing n-variate (n+k)-nomials for small k. 1457-1469