Volume 410; Issue 8-10

Theoretical Computer Science

Volume 410; Issue 8-10
2

Adversarial queuing theory with setups

M. Kiwi, M. Soto, C. Thraves
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 1.25 MB
english, 2009
3

The degree distribution of random -trees

Yong Gao
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 515 KB
english, 2009
4

Treewidth and logical definability of graph products

Selma Djelloul
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 963 KB
english, 2009
5

A more effective linear kernelization for cluster editing

Jiong Guo
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 702 KB
english, 2009
6

The antimagicness of the Cartesian product of graphs

Yuchen Zhang, Xiaoming Sun
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 683 KB
english, 2009
7

Short fail-stop signature scheme based on factorization and discrete logarithm assumptions

Willy Susilo
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 569 KB
english, 2009
9

Compressed depth sequences

Travis Gagie
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 476 KB
english, 2009
12

A generalization of Thue freeness for partial words

F. Blanchet-Sadri, Robert Mercaş, Geoffrey Scott
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 525 KB
english, 2009
13

Approximation of the -batch consolidation problem

Sung-Pil Hong, Myoung-Ju Park, Soo Y. Chang
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 484 KB
english, 2009
14

Single machine parallel-batch scheduling with deteriorating jobs

Xianglai Qi, Shiguo Zhou, Jinjiang Yuan
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 490 KB
english, 2009
15

Fault-free longest paths in star networks with conditional link faults

Ping-Ying Tsai, Jung-Sheng Fu, Gen-Huey Chen
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 1.30 MB
english, 2009
16

A quadratic algorithm for the 2-cyclic robotic scheduling problem

Pablo Sáez
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 441 KB
english, 2009
18

Two semi-online scheduling problems on two uniform machines

C.T. Ng, Zhiyi Tan, Yong He, T.C.E. Cheng
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 1.13 MB
english, 2009
19

The complexity of the matroid–greedoid partition problem

Vera Asodi, Christopher Umans
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 525 KB
english, 2009
20

A constrained edit distance algorithm between semi-ordered trees

Aïda Ouangraoua, Pascal Ferraro
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 925 KB
english, 2009
23

-difference matching in amortized linear time for all the words in a text

Cinzia Pizzi
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 556 KB
english, 2009
24

Efficient computation of the iteration of functions

Tsung-Hsi Tsai
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 792 KB
english, 2009
25

On the complexity of approximating the Hadwiger number

Martin Wahlén
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 356 KB
english, 2009
27

Constructing edge-disjoint spanning trees in locally twisted cubes

Sun-Yuan Hsieh, Chang-Jen Tu
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 740 KB
english, 2009
28

On the simplification of infinite morphic words

Juha Honkala
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 302 KB
english, 2009
29

Overlap-freeness in infinite partial words

Vesa Halava, Tero Harju, Tomi Kärki, Patrice Séébold
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 415 KB
english, 2009
30

On the support size of stable strategies in random games

Spyros C. Kontogiannis, Paul G. Spirakis
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 587 KB
english, 2009
32

On the pseudo-achromatic number problem

Jianer Chen, Iyad A. Kanj, Jie Meng, Ge Xia, Fenghui Zhang
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 1.04 MB
english, 2009
33

Testing avoidability on sets of partial words is hard

F. Blanchet-Sadri, Raphaël M. Jungers, Justin Palumbo
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 333 KB
english, 2009
34

A -approximation algorithm for minimum weighted dominating set in unit disk graph

Decheng Dai, Changyuan Yu
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 919 KB
english, 2009
36

Dynamic TCP acknowledgment with sliding window

Hisashi Koga
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 825 KB
english, 2009
37

Improved approximation bounds for edge dominating set in dense graphs

Jean Cardinal, Stefan Langerman, Eythan Levy
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 747 KB
english, 2009
38

The subdivision-constrained minimum spanning tree problem

Jianping Li, Weidong Li, Tongquan Zhang, Zhongxu Zhang
Journal:
Theoretical Computer Science
Year:
2009
Language:
english
File:
PDF, 734 KB
english, 2009