Volume 411; Issue 16-18

Theoretical Computer Science

Volume 411; Issue 16-18
1

Average-case analysis for the MAX-2SAT problem

Osamu Watanabe, Masaki Yamamoto
Journal:
Theoretical Computer Science
Year:
2010
Language:
english
File:
PDF, 419 KB
english, 2010
2

Parameterized algorithms for -Hitting Set: The weighted case

Henning Fernau
Journal:
Theoretical Computer Science
Year:
2010
Language:
english
File:
PDF, 614 KB
english, 2010
4

Optimal bounds on finding fixed points of contraction mappings

Ching-Lueh Chang, Yuh-Dauh Lyuu
Journal:
Theoretical Computer Science
Year:
2010
Language:
english
File:
PDF, 313 KB
english, 2010
5

Rotations in the stable -matching problem

Viera Borbel’ová, Katarína Cechlárová
Journal:
Theoretical Computer Science
Year:
2010
Language:
english
File:
PDF, 515 KB
english, 2010
6

Distributional analysis of swaps in Quick Select

Hosam M. Mahmoud
Journal:
Theoretical Computer Science
Year:
2010
Language:
english
File:
PDF, 286 KB
english, 2010
7

Bounded sequence testing from deterministic finite state machines

Florentin Ipate
Journal:
Theoretical Computer Science
Year:
2010
Language:
english
File:
PDF, 543 KB
english, 2010
8

The hitting and cover times of Metropolis walks

Yoshiaki Nonaka, Hirotaka Ono, Kunihiko Sadakane, Masafumi Yamashita
Journal:
Theoretical Computer Science
Year:
2010
Language:
english
File:
PDF, 311 KB
english, 2010
9

Multiway in-place merging

Viliam Geffert, Jozef Gajdoš
Journal:
Theoretical Computer Science
Year:
2010
Language:
english
File:
PDF, 642 KB
english, 2010
10

Codes and maximal monoids

Sujin Shin
Journal:
Theoretical Computer Science
Year:
2010
Language:
english
File:
PDF, 343 KB
english, 2010
11

Criteria for the matrix equivalence of words

Arto Salomaa
Journal:
Theoretical Computer Science
Year:
2010
Language:
english
File:
PDF, 350 KB
english, 2010
12

The biased, distance-restricted -in-a-row game for small

Cheng W. Hong
Journal:
Theoretical Computer Science
Year:
2010
Language:
english
File:
PDF, 202 KB
english, 2010
13

On convex complexity measures

P. Hrubeš, S. Jukna, A. Kulikov, P. Pudlák
Journal:
Theoretical Computer Science
Year:
2010
Language:
english
File:
PDF, 389 KB
english, 2010
14

All-to-all personalized exchange in generalized shuffle-exchange networks

Well Y. Chou, Chiuyuan Chen
Journal:
Theoretical Computer Science
Year:
2010
Language:
english
File:
PDF, 1.43 MB
english, 2010
15

On exponential time lower bound of Knapsack under backtracking

Xin Li, Tian Liu
Journal:
Theoretical Computer Science
Year:
2010
Language:
english
File:
PDF, 284 KB
english, 2010
18

Transducers for the bidirectional decoding of prefix codes

Laura Giambruno, Sabrina Mantaci
Journal:
Theoretical Computer Science
Year:
2010
Language:
english
File:
PDF, 383 KB
english, 2010
19

Size versus stability in the marriage problem

Péter Biró, David F. Manlove, Shubham Mittal
Journal:
Theoretical Computer Science
Year:
2010
Language:
english
File:
PDF, 451 KB
english, 2010
20

Non-cooperative facility location and covering games

Jean Cardinal, Martin Hoefer
Journal:
Theoretical Computer Science
Year:
2010
Language:
english
File:
PDF, 656 KB
english, 2010
21

Single-machine scheduling under the job rejection constraint

Liqi Zhang, Lingfa Lu, Jinjiang Yuan
Journal:
Theoretical Computer Science
Year:
2010
Language:
english
File:
PDF, 273 KB
english, 2010