Volume 410; Issue 21-23

Theoretical Computer Science

Volume 410; Issue 21-23
2

Paths, cycles and circular colorings in digraphs

Guanghui Wang, Guizhen Liu
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 360 KB
english, 2009
3

Fast neighbor joining

Isaac Elias, Jens Lagergren
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 561 KB
english, 2009
4

On parameterized complexity of the Multi-MCS problem

Wenbin Chen, Matthew C. Schmidt, Nagiza F. Samatova
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 556 KB
english, 2009
6

Moves and displacements of particular elements in Quicksort

Conrado Martínez, Helmut Prodinger
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 393 KB
english, 2009
7

The complexity of clique graph recognition

Liliana Alcón, Luerbio Faria, Celina M.H. de Figueiredo, Marisa Gutierrez
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 1.81 MB
english, 2009
8

Morphically primitive words

Daniel Reidenbach, Johannes C. Schneider
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 836 KB
english, 2009
9

Asymptotic subword complexity of fixed points of group substitutions

Ilya Goldstein
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 1.01 MB
english, 2009
10

Quasi-linear transformations and discrete tilings

M.-A. Jacob-Da Col, P. Tellier
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 1.33 MB
english, 2009
11

Classifying rendezvous tasks of arbitrary dimension

Xingwu Liu, Zhiwei Xu, Jianzhong Pan
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 1.30 MB
english, 2009
12

Inapproximability of survivable networks

Yuval Lando, Zeev Nutov
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 414 KB
english, 2009
13

Collapsing words, permutation conditions and coherent colorings of trees

A. Cherubini, A. Kisielewicz
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 964 KB
english, 2009
15

Truthful mechanisms for two-range-values variant of unrelated scheduling

Changyuan Yu
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 568 KB
english, 2009
16

Minimal achievable approximation ratio for MAX-MQ in finite fields

Shang-Wei Zhao, Xiao-Shan Gao
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 401 KB
english, 2009
19

A best online algorithm for scheduling on two parallel batch machines

Ji Tian, Ruyan Fu, Jinjiang Yuan
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 388 KB
english, 2009
20

Coloring Artemis graphs

Benjamin Lévêque, Frédéric Maffray, Bruce Reed, Nicolas Trotignon
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 503 KB
english, 2009
21

Matrix columns allocation problems

Amos Beimel, Boaz Ben-Moshe, Yehuda Ben-Shimol, Paz Carmi, Eldad Chai, Itzik Kitroser, Eran Omri
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 859 KB
english, 2009
22

Approximation hardness of deadline-TSP reoptimization

Hans-Joachim Böckenhauer, Joachim Kneis, Joachim Kupke
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 871 KB
english, 2009
23

Finding a tree structure in a resolution proof is NP-complete

Jan Hoffmann
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 472 KB
english, 2009
24

Maximum scan statistics and channel assignment problems in homogeneous wireless networks

Chih-Wei Yi
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 751 KB
english, 2009
25

Deterministic bottom-up tree transducers and ground term rewrite systems

Sándor Vágvölgyi
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 2.03 MB
english, 2009
26

The simultaneous consecutive ones problem

Marcus Oswald, Gerhard Reinelt
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 622 KB
english, 2009
28

Non-mitotic sets

Christian Glaßer, Alan L. Selman, Stephen Travers, Liyu Zhang
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 833 KB
english, 2009
29

Compound Node–Kayles on paths

Adrien Guignard, Éric Sopena
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 650 KB
english, 2009
32

Tight rank lower bounds for the Sherali–Adams proof system

Stefan Dantchev, Barnaby Martin, Mark Rhodes
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 718 KB
english, 2009
33

Online scheduling on two uniform machines to minimize the makespan

Ming Liu, Yinfeng Xu, Chengbin Chu, Feifeng Zheng
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 650 KB
english, 2009