Volume 562

Theoretical Computer Science

Volume 562
3

Approximation algorithms for digraph width parameters

Kintali, Shiva, Kothari, Nishad, Kumar, Akash
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 758 KB
english, 2015
4

Succinct representation of labeled trees

Tsur, Dekel
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 582 KB
english, 2015
7

Concurrent signature without random oracles

Tan, Xiao, Huang, Qiong, Wong, Duncan S.
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 1010 KB
english, 2015
8

Bounding the payment of approximate truthful mechanisms

Calinescu, Gruia
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 1.03 MB
english, 2015
13

Memoryless computation: New results, constructions, and extensions

Gadouleau, Maximilien, Riis, Søren
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 500 KB
english, 2015
16

The benefit of adaptivity in stochastic packing problems with probing

Levin, Asaf, Vainer, Aleksander
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 361 KB
english, 2015
17

Competitive analysis of maintaining frequent items of a stream

Giannakopoulos, Yiannis, Koutsoupias, Elias
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 345 KB
english, 2015
18

Inapproximability of dominating set on power law graphs

Gast, Mikael, Hauptmann, Mathias, Karpinski, Marek
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 654 KB
english, 2015
19

Using swaps and deletes to make strings match

Meister, Daniel
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 433 KB
english, 2015
20

A note on short palindromes in square-free words

Harju, Tero, Müller, Mike
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 150 KB
english, 2015
21

On the commutative equivalence of semi-linear sets of

D'Alessandro, Flavio, Intrigila, Benedetto
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 519 KB
english, 2015
22

On the complexity of the traveling umpire problem

de Oliveira, Lucas, de Souza, Cid C., Yunes, Tallys
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 357 KB
english, 2015
23

Randomized algorithms for online knapsack problems

Han, Xin, Kawase, Yasushi, Makino, Kazuhisa
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 353 KB
english, 2015
24

Independent dominating set problem revisited

Liu, Ching-Hao, Poon, Sheung-Hung, Lin, Jin-Yong
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 957 KB
english, 2015
26

On t-extensions of the Hankel determinants of certain automatic sequences

Fu, Hao, Han, Guo-Niu
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 304 KB
english, 2015
27

Improving the Hk

Disser, Yann, Feldmann, Andreas Emil, Klimm, Max, Mihalák, Matúš
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 341 KB
english, 2015
29

Combinatorics for smaller kernels: The differential of a graph

Bermudo, Sergio, Fernau, Henning
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 1.15 MB
english, 2015
31

One-to-one disjoint path covers on alternating group graphs

You, Lantao, Fan, Jianxi, Han, Yuejuan, Jia, Xiaohua
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 1.71 MB
english, 2015
32

Computing on binary strings

Bu, Tian-Ming, Yuan, Chen, Zhang, Peng
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 286 KB
english, 2015
34

Solution to a conjecture on words that are bad and 2-isometric

Wei, Jianxin, Zhang, Heping
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 307 KB
english, 2015
35

A PTAS for the Square Tiling Problem

Amir, Amihood, Apostolico, Alberto, Landau, Gad M., Porat, Ely, Sar Shalom, Oren
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 469 KB
english, 2015
36

Exact algorithms for Kayles

Bodlaender, Hans L., Kratsch, Dieter, Timmer, Sjoerd T.
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 452 KB
english, 2015
39

Postfix automata

Jing, Maohua, Yang, Yixian, Lu, Ning, Shi, Wenbo, Yu, Changyong
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 637 KB
english, 2015
40

The ring design game with fair cost allocation

Fanelli, Angelo, Leniowski, Dariusz, Monaco, Gianpiero, Sankowski, Piotr
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 396 KB
english, 2015
41

Voronoi game on graphs

Bandyapadhyay, Sayan, Banik, Aritra, Das, Sandip, Sarkar, Hirak
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 514 KB
english, 2015
42

Optimistic fair exchange in the enhanced chosen-key model

Wang, Yang, Au, Man Ho, Susilo, Willy
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 552 KB
english, 2015
44

Finding a subdivision of a digraph

Bang-Jensen, Jørgen, Havet, Frédéric, Karolinna Maia, A.
Journal:
Theoretical Computer Science
Year:
2015
Language:
english
File:
PDF, 603 KB
english, 2015
47

Editorial Board

Journal:
Theoretical Computer Science
Year:
2015
File:
PDF, 70 KB
2015