Discrete Mathematics & Theoretical Computer Science, Volume 8

Volume 8, Number 1, 2006

Analysis of Algorithms

Enrico Angelelli, Maria Grazia Speranza, Zsolt Tuza:
New bounds and algorithms for on-line scheduling: two identical processors, known sum and upper bound on the tasks. 1-16
R. Balasubramanian, C. R. Subramanian:
On Sampling Colorings of Bipartite Graphs. 17-30
Ludger Rüschendorf, Ralf Neininger:
Survey of Multivariate Aspects of the Contraction Method. 31-56
Ed Hong:
The Online Specialization Problem. 97-120
Alan M. Frieze, Juan Vera:
On randomly colouring locally sparse graphs. 121-128
Arnold Knopfmacher, Helmut Prodinger:
The first descent in samples of geometric random variables and permutations. 215-234
Stavros D. Nikolopoulos, Charis Papadopoulos:
On the number of spanning trees of K_n^m±G graphs. 235-248
Helmut Prodinger: d-records in geometrically distributed random variables. 273-284

Automata, Logic and Semantics

Jakob Grue Simonsen:
On the Computability of the Topological Entropy of Subshifts. 83-96
Samy Abbes:
A Cartesian closed category of event structures with quotients. 249-272

Combinatorics

Sylvie Corteel, Guy Louchard, Robin Pemantle:
Common intervals in permutations. 189-214
Toufik Mansour, Basel Sirhan:
Counting l-letter subwords in compositions. 285-298

Distributed Computing and Networking

Bao-Xing Chen, Ji-Xiang Meng, Wenjun Xiao:
Some new optimal and suboptimal infinite families of undirected double-loop networks. 299-312

Graphs and Algorithms

Mekkia Kouider, Preben D. Vestergaard:
Generalized connected domination in graphs. 57-64
Stavros D. Nikolopoulos, Leonidas Palios:
Recognizing HH-free, HHD-free, and Welsh-Powell Opposition Graphs. 65-82
Tiziana Calamoneri:
Optimal L(h, k)-Labeling of Regular Grids. 141-158
Mustapha Kchikech, Olivier Togni:
Approximation Algorithms for Multicoloring Planar Graphs and Powers of Square and Triangular Meshes. 159-172
Andreas Brandstädt, Tilo Klembt, Suhail Mahfud:
P₆- and triangle-free graphs revisited: structure and bounded clique-width. 173-188

General