Volume 348; Issue 2-3

Theoretical Computer Science

Volume 348; Issue 2-3
1

Preface

Josep Díaz, Juhani Karhumaki
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 99 KB
english, 2005
3

Locally consistent constraint satisfaction problems

Zdeněk Dvořák, Daniel Král’, Ondřej Pangrác
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 318 KB
english, 2005
4

Linear tolls suffice: New bounds and algorithms for tolls in single source networks

Lisa Fleischer
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 206 KB
english, 2005
5

Simple permutations mix well

Shlomo Hoory, Avner Magen, Steven Myers, Charles Rackoff
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 226 KB
english, 2005
6

The black-box complexity of nearest-neighbor search

Robert Krauthgamer, James R. Lee
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 373 KB
english, 2005
7

Regular solutions of language inequalities and well quasi-orders

Michal Kunc
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 300 KB
english, 2005
8

Close to optimal decentralized routing in long-range contact networks

Emmanuelle Lebhar, Nicolas Schabanel
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 483 KB
english, 2005
9

A time lower bound for satisfiability

Dieter van Melkebeek, Ran Raz
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 208 KB
english, 2005
10

LA, permutations, and the Hajós Calculus

Michael Soltys
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 244 KB
english, 2005
11

Efficiently computing succinct trade-off curves

Sergei Vassilvitskii, Mihalis Yannakakis
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 447 KB
english, 2005
12

A new algorithm for optimal 2-constraint satisfaction and its implications

Ryan Williams
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 215 KB
english, 2005
13

Selfish unsplittable flows

Dimitris Fotakis, Spyros Kontogiannis, Paul Spirakis
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 272 KB
english, 2005
14

Author index

Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 129 KB
english, 2005
15

The complexity of partition functions

Andrei Bulatov, Martin Grohe
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 488 KB
english, 2005
16

On graph problems in a semi-streaming model

Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, Jian Zhang
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 207 KB
english, 2005
17

The minimum-entropy set cover problem

Eran Halperin, Richard M. Karp
Journal:
Theoretical Computer Science
Year:
2005
Language:
english
File:
PDF, 230 KB
english, 2005