


default search action
Theoretical Computer Science, Volume 411
Volume 411, Number 1, January 2010
- Dorit S. Hochbaum, Asaf Levin
:
Covering the edges of bipartite graphs using K2, 2 graphs. 1-9 - Laurent Lyaudet:
NP-hard and linear variants of hypergraph partitioning. 10-21 - Kohtaro Tadaki, Tomoyuki Yamakami, Jack C. H. Lin:
Theory of one-tape linear-time Turing machines. 22-43 - Leah Epstein, Rob van Stee:
Maximizing the minimum load for selfish agents. 44-57 - Achour Mostéfaoui, Michel Raynal, Corentin Travers:
Narrowing power vs efficiency in synchronous set agreement: Relationship, algorithms and lower bound. 58-69 - Aldo de Luca, Luca Q. Zamboni:
On graphs of central episturmian words. 70-90 - Gem Stapleton, John Howse
, Peter J. Rodgers
:
A graph theoretic approach to general Euler diagram drawing. 91-112 - Markus Müller:
Stationary algorithmic probability. 113-130 - Marek Chrobak, Jirí Sgall
:
Three results on frequency assignment in linear cellular networks. 131-137 - Martin Anthony
, Joel Ratsaby:
Maximal width learning of binary functions. 138-147 - Donatella Merlini
, Renzo Sprugnoli:
The relevant prefixes of coloured Motzkin walks: An average case analysis. 148-163 - Hartwig Bosse, Jaroslaw Byrka, Evangelos Markakis:
New algorithms for approximate Nash equilibria in bimatrix games. 164-173 - Xiang-Yang Li, Zheng Sun, Weizhao Wang, Xiaowen Chu
, Shaojie Tang, Ping Xu:
Mechanism design for set cover games with selfish element agents. 174-187 - Ulrich Laube, Markus E. Nebel:
Maximum likelihood analysis of algorithms and data structures. 188-212 - Paolo D'Arco, Alfredo De Santis
, Anna Lisa Ferrara, Barbara Masucci
:
Variations on a theme by Akl and Taylor: Security and tradeoffs. 213-227 - Yun Liu:
Compositions of maximal codes. 228-238 - Allan Borodin, Joan Boyar
, Kim S. Larsen
, Nazanin Mirmohammadi:
Priority algorithms for graph optimization problems. 239-258 - David Richeson
, Paul Winkler, Jim Wiseman:
Itineraries of rigid rotations and diffeomorphisms of the circle. 259-265 - Véronique Terrier:
Simulation of one-way cellular automata by boolean circuits. 266-276 - Mingen Lin, Yang Yang, Jinhui Xu:
On Lazy Bin Covering and Packing problems. 277-284
- Md. Kamrul Hasan, Mohammad Kaykobad, Young-Koo Lee, Sungyoung Lee:
A comprehensive analysis of degree based condition for Hamiltonian cycles. 285-287 - Andrzej Chmielowiec
:
Fixed points of the RSA encryption algorithm. 288-292 - Ye Du, Rahul Sami, Yaoyun Shi:
Path auctions with multiple edge ownership. 293-300
Volume 411, Number 2, January 2010
- Ken Kaneiwa, Ken Satoh:
On the complexities of consistency checking for restricted UML class diagrams. 301-323 - Ken-etsu Fujita:
CPS-translation as adjoint. 324-340 - Stephen L. Bloom, Zoltán Ésik:
A Mezei-Wright theorem for categorical algebras. 341-359 - Lan Lin, Stacy J. Prowell
, Jesse H. Poore:
An axiom system for sequence-based specification. 360-376 - Ugo Dal Lago
, Andrea Masini, Margherita Zorzi
:
Quantum implicit computational complexity. 377-409 - Michele Pagani
, Lorenzo Tortora de Falco
:
Strong normalization property for second order linear logic. 410-444 - Manuel Bodirsky
, Hubie Chen:
Peek arc consistency. 445-453 - Laura Bozzelli, Ruggero Lanotte
:
Complexity and succinctness issues for linear-time hybrid logics. 454-469 - Patrick Baillot, Damiano Mazza:
Linear logic by levels and bounded time complexity. 470-503 - María Alpuente
, Santiago Escobar
, Bernhard Gramlich, Salvador Lucas
:
On-demand strategy annotations revisited: An improved on-demand evaluation strategy. 504-541 - Alessandro Romanel
, Corrado Priami:
On the computational power of BlenX. 542-565 - Robert M. Hierons
:
Canonical finite state machines for distributed systems. 566-580
Volume 411, Number 3, January 2010
- Oscar H. Ibarra, Juhani Karhumäki, Alexander Okhotin
:
On stateless multihead automata: Hierarchies and the emptiness problem. 581-593 - Thi Ha Duong Phan, Tran Thi Thu Huong:
On the stability of Sand Piles Model. 594-601 - Bart Kastermans, Steffen Lempp:
Comparing notions of randomness. 602-616 - Elena Czeizler, Lila Kari, Shinnosuke Seki:
On a special class of primitive words. 617-630 - Christian Mathissen:
Definable transductions and weighted logics for texts. 631-659 - Vittorio Bilò
, Angelo Fanelli
, Michele Flammini
, Luca Moscardelli:
When ignorance helps: Graphical multicast cost sharing games. 660-671 - Wanyong Tian, Minming Li
, Enhong Chen:
Energy optimal schedules for jobs with multiple active intervals. 672-676
- Colm Ó'Dúnlaing, Natalie Schluter:
A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systems. 677-690 - Mario Boley
, Tamás Horváth, Axel Poigné, Stefan Wrobel:
Listing closed sets of strongly accessible set systems with applications to data mining. 691-700
Volume 411, Numbers 4-5, January 2010
- Erzsébet Csuhaj-Varjú, Zoltán Ésik:
Preface. 701
- Henrik Björklund, Thomas Schwentick:
On notions of regularity for data languages. 702-715 - Gaëlle Brevier, Romeo Rizzi
, Stéphane Vialette:
Complexity issues in color-preserving graph embeddings. 716-729 - Robert Brijder
, Miika Langille, Ion Petre
:
Extended strings and graphs for simple gene assembly. 730-738 - Jin-yi Cai, Pinyan Lu
:
On blockwise symmetric signatures for matchgates. 739-750 - Thomas Colcombet:
Factorization forests for infinite words and applications to countable scattered linear orderings. 751-764 - Jörg Endrullis
, Clemens Grabmayer, Dimitri Hendriks, Ariya Isihara, Jan Willem Klop:
Productivity of stream definitions. 765-782 - Edith Hemaspaandra, Lane A. Hemaspaandra
, Till Tantau, Osamu Watanabe:
On the complexity of kings. 783-798 - Michael Hoffmann, Richard M. Thomas:
Notions of hyperbolicity in monoids. 799-811 - Martin Kutrib
, Andreas Malcher
:
Real-time reversible iterative arrays. 812-822 - Andrea Sattler-Klein:
Some complexity results for prefix Gröbner bases in free monoid rings. 823-833
Volume 411, Number 6, February 2010
- Grzegorz Rozenberg:
Preface. 835-836
- Shlomi Dolev
, Hen Fitoussi:
Masking traveling beams: Optical solutions for NP-complete problems, trading space for time. 837-853 - Tobias Friedrich, Nils Hebbinghaus, Frank Neumann
:
Plateaus can be harder in multi-objective optimization. 854-864 - Paola Bonizzoni
:
Constants and label-equivalence: A decision procedure for reflexive regular splicing languages. 865-877 - Antonio E. Porreca
, Giancarlo Mauri
, Claudio Zandron:
Non-confluence in divisionless P systems with active membranes. 878-887 - Xingchang Liu, Xiaofan Yang, Shenglin Li, Yong Ding:
Solving the minimum bisection problem using a biologically inspired computational model. 888-896 - Robert Brijder
, Hendrik Jan Hoogeboom
:
Combining overlap and containment for gene assembly in ciliates. 897-905 - Linqiang Pan
, Gheorghe Paun:
Spiking neural P systems: An improved normal form. 906-918 - J. Mark Keil, Jing Liu, Ian McQuillan
:
Algorithmic properties of ciliate sequence alignment. 919-925 - Tianshi Chen, Jun He
, Guoliang Chen, Xin Yao
:
Choosing selection pressure for wide-gap problems. 926-934
Volume 411, Numbers 7-9, February 2010
- Reinhard Pichler, Vadim Savenkov
:
Towards practical feasibility of core computation in data exchange. 935-957 - Mauro Mezzini
, Marina Moscarini
:
Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network. 958-966 - Katerina Asdre, Stavros D. Nikolopoulos:
A polynomial solution to the k-fixed-endpoint path cover problem on proper interval graphs. 967-975 - Matthew de Brecht, Akihiro Yamamoto:
Mind change complexity of inferring unbounded unions of restricted pattern languages from positive data. 976-985 - Tien-Ching Lin, D. T. Lee:
Efficient algorithms for the sum selection problem and k maximum sums problem. 986-994 - Sadish Sadasivam, Huaming Zhang:
NP-Completeness of st-orientations for plane graphs. 995-1003 - Elaine Render, Mark Kambites:
Semigroup automata with rational initial and terminal sets. 1004-1012 - Serafino Cicerone
, Gianlorenzo D'Angelo
, Gabriele Di Stefano, Daniele Frigioni
:
Partially dynamic efficient algorithms for distributed shortest paths. 1013-1037 - Yukun Cheng, Liying Kang, Changhong Lu:
The pos/neg-weighted 1-median problem on tree graphs with subtree-shaped customers. 1038-1044 - Fedor V. Fomin
, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Saket Saurabh:
Iterative compression and exact algorithms. 1045-1053 - Petra Berenbrink, Oliver Schulte:
Evolutionary equilibrium in Bayesian routing games: Specialization and niche formation. 1054-1074 - Pietro di Lena
, Luciano Margara
:
On the undecidability of the limit behavior of Cellular Automata. 1075-1084 - Chaim Goodman-Strauss:
A hierarchical strongly aperiodic set of tiles in the hyperbolic plane. 1085-1093 - Zhenbo Wang, Wenxun Xing, Shu-Cherng Fang:
Two-group knapsack game. 1094-1103 - Jeff Abrahamson, Ali Shokoufandeh:
Euclidean TSP on two polygons. 1104-1114 - Pawel Gawrychowski, Marin Gutan, Andrzej Kisielewicz:
On the problem of freeness of multiplicative matrix semigroups. 1115-1120 - Carlos Gómez-Rodríguez
, Miguel A. Alonso
, Manuel Vilares Ferro:
Error-repair parsing schemata. 1121-1139 - Shenpeng Lu, Haodi Feng, Xiuqian Li:
Minimizing the makespan on a single parallel batching machine. 1140-1145 - Nicolas Gast, Bruno Gaujal:
Infinite labeled trees: From rational to Sturmian trees. 1146-1166 - Fedor V. Fomin
, Petr A. Golovach
, Jan Kratochvíl
, Nicolas Nisse, Karol Suchan
:
Pursuing a fast robber on a graph. 1167-1181 - Kazuo Iwama, Kazuhisa Seto
, Suguru Tamaki:
The complexity of the Hajós calculus for planar graphs. 1182-1191 - Oscar H. Ibarra, Igor Potapov, Hsu-Chun Yen:
On decision problems for parameterized machines. 1192-1201 - Hans L. Bodlaender
, Michael R. Fellows
, Pinar Heggernes
, Federico Mancini, Charis Papadopoulos
, Frances A. Rosamond
:
Clustering with partial information. 1202-1211 - Mauro Mezzini
:
On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs. 1212-1220 - Raphael C. S. Machado, Celina M. H. de Figueiredo
, Kristina Vuskovic:
Chromatic index of graphs with no cycle with a unique chord. 1221-1234
Volume 411, Number 10, March 2010
- Moti Yung:
Preface. 1235
- Marius Zimand:
Simple extractors via constructions of cryptographic pseudo-random generators. 1236-1250 - Omer Horvitz, Jonathan Katz:
Bounds on the efficiency of black-box commitment schemes. 1251-1260 - Yannick Chevalier
, Michaël Rusinowitch:
Symbolic protocol analysis in the union of disjoint intruder theories: Combining decision procedures. 1261-1282 - Tal Moran, Moni Naor:
Basing cryptographic protocols on tamper-evident seals. 1283-1310
Volume 411, Numbers 11-13, March 2010
- Jifeng He, Tony Hoare:
CSP is a retract of CCS. 1311-1337 - Simona Orzan, Tim A. C. Willemse
:
Invariants for Parameterised Boolean Equation Systems. 1338-1371 - Richard W. Barraclough, David W. Binkley, Sebastian Danicic, Mark Harman
, Robert M. Hierons
, Ákos Kiss, Mike Laurence, Lahcen Ouarbya:
A trajectory-based strict semantics for program slicing. 1372-1386 - Yuxi Fu, Hao Lu:
On the expressiveness of interaction. 1387-1451 - Philippe Gaucher
:
Combinatorics of labelling in higher-dimensional automata. 1452-1483 - Sandra Alves
, Maribel Fernández
, Mário Florido
, Ian Mackie:
Gödel's system tau revisited. 1484-1500 - Peter Hines:
Quantum circuit oracles for Abstract Machine computations. 1501-1520 - Manfred Schmidt-Schauß, David Sabel
:
On generic context lemmas for higher-order calculi with sharing. 1521-1541
Volume 411, Numbers 14-15, March 2010
- Alexander A. Shvartsman
, Pascal Felber
:
Editors' preface. 1543
- David Ilcinkas, Dariusz R. Kowalski, Andrzej Pelc:
Fast radio broadcasting with advice. 1544-1557 - Florent Becker, Sergio Rajsbaum
, Ivan Rapaport
, Eric Rémila:
Average long-lived binary consensus: Quantifying the stabilizing role played by memory. 1558-1566 - Toshimitsu Masuzawa, Sébastien Tixeuil:
Quiescence of self-stabilizing gossiping among mobile agents in graphs. 1567-1582 - Paola Flocchini, David Ilcinkas, Andrzej Pelc, Nicola Santoro
:
Remembering without memory: Tree exploration by asynchronous oblivious robots. 1583-1598 - Thomas Sauerwald, Dirk Sudholt:
A self-stabilizing algorithm for cut problems in synchronous networks. 1599-1612 - Pierre Fraigniaud, Emmanuelle Lebhar, Zvi Lotker:
Recovering the long-range links in augmented graphs. 1613-1625 - Davide Bilò
, Thomas Erlebach
, Matús Mihalák, Peter Widmayer:
Discovery of network properties with all-shortest-paths queries. 1626-1637 - Colin Cooper, Ralf Klasing, Tomasz Radzik
:
Locating and repairing faults in a network with mobile agents. 1638-1647 - David Adjiashvili, David Peleg:
Equal-area locus-based convex polygon decomposition. 1648-1667
Volume 411, Numbers 16-18, March 2010
- Well Y. Chou, Chiuyuan Chen:
All-to-all personalized exchange in generalized shuffle-exchange networks. 1669-1684 - Osamu Watanabe, Masaki Yamamoto:
Average-case analysis for the MAX-2SAT problem. 1685-1697 - Henning Fernau
:
Parameterized algorithms for d-Hitting Set: The weighted case. 1698-1713 - Katsuhisa Yamanaka, Shin-Ichi Nakano, Yasuko Matsui, Ryuhei Uehara
, Kento Nakada:
Efficient enumeration of all ladder lotteries and its application. 1714-1722 - Joxe Gaintzarain
, Montserrat Hermo
, Paqui Lucio
, Marisa Navarro
:
Translating propositional extended conjunctions of Horn clauses into Boolean circuits. 1723-1733 - Martin R. Ehmsen, Lene M. Favrholdt
, Jens S. Kohrt, Rodica Mihai
:
Comparing First-Fit and Next-Fit for online edge coloring. 1734-1741 - Ching-Lueh Chang, Yuh-Dauh Lyuu
:
Optimal bounds on finding fixed points of contraction mappings. 1742-1749 - Viera Borbel'ová, Katarína Cechlárová
:
Rotations in the stable b-matching problem. 1750-1762 - Hosam M. Mahmoud
:
Distributional analysis of swaps in Quick Select. 1763-1769 - Florentin Ipate:
Bounded sequence testing from deterministic finite state machines. 1770-1784 - Laura Giambruno, Sabrina Mantaci:
Transducers for the bidirectional decoding of prefix codes. 1785-1792 - Viliam Geffert, Jozef Gajdos:
Multiway in-place merging. 1793-1808 - Sujin Shin:
Codes and maximal monoids. 1809-1817 - Arto Salomaa:
Criteria for the matrix equivalence of words. 1818-1827 - Péter Biró, David F. Manlove
, Shubham Mittal:
Size versus stability in the marriage problem. 1828-1841 - Pavel Hrubes, Stasys Jukna
, Alexander S. Kulikov
, Pavel Pudlák:
On convex complexity measures. 1842-1854 - Jean Cardinal, Martin Hoefer:
Non-cooperative facility location and covering games. 1855-1876 - Liqi Zhang
, Lingfa Lu
, Jinjiang Yuan:
Single-machine scheduling under the job rejection constraint. 1877-1882