Discrete Mathematics & Theoretical Computer Science

Warning: Due to massif spamming of our user database, it is currently not possible to create new user ids via our web interface. We hope to resolve this problem soon. In the mean time, if you want to do a submission to DMTCS and do not yet have a user id here, please contact us directly by mail and we will create it for you.


  • Analysis of Algorithms
  • Automata, Logic and Semantics
  • Combinatorics
  • Discrete Algorithms
  • Distributed Computing and Networking
  • Graph Theory

The journal is devoted to a quest of quality and immediacy. The median value for acceptance of papers (including refereeing and all eventual revisions) has been about 12 month for papers submitted in 2011.

Author's manuscripts are published as soon as they have been accepted and the authors provide the final LaTeX sources, They are freely available via the Internet. Due to the combined efforts of our authors (who typeset their final document with our LaTeX style) and our volunteers (who do the final layout) the time between reception of the sources and final publication has a median of 2 weeks.

DMTCS is published by a French association of the same name in cooperation with the Laboratoire Lorrain de Recherche en Informatique et ses Applications, LORIA, in Nancy, France, which provides us with our primary server.

Vol 16, No 1 (2014)

Table of Contents


Computation with No Memory, and Rearrangeable Multicast Networks PDF PostScript
Serge Burckel, Emeric Gioan, Emmanuel Thomé 121-142

Automata, Logic and Semantics

Canonical forms for free κ-semigroups PDF PostScript
José Carlos Costa 159-178


Descents after maxima in compositions PDF PostScript
Aubrey Blecher, Charlotte Brennan, Arnold Knopfmacher 61-72
Graphs where every k-subset of vertices is an identifying set PDF
Sylvain Gravier, Svante Janson, Tero Laihonen, Sanna Maarit Ranto 73-88

Discrete Algorithms

The Price of Mediation PDF PostScript
Milan Bradonjic, Gunes Ercal, Adam Meyerson, Alan Roytman 31-60
An Amortized Search Tree Analysis for Finding a k-Leaf Spanning Tree in an Undirected Graph PDF PostScript
Daniel Binkele-Raible, Henning Fernau 179-200

Graph Theory

On size, radius and minimum degree PDF PostScript
Simon Mukwembi 1-6
On Hamiltonian Paths and Cycles in Sufficiently Large Distance Graphs PDF PostScript
Christian Löwenstein, Dieter Rautenbach, Roman Soták 7-30
List circular backbone colouring PDF PostScript
Frederic Havet, Andrew King 89-104
Efficient open domination in graph products PDF PostScript
Dorota Kuziak, Iztok Peterin, Ismael Gonzalez Yero 105-120
Strong parity vertex coloring of plane graphs PDF PostScript
Tomáš Kaiser, Ondřej Rucký, Matěj Stehlík, Riste Škrekovski 143-158
The Total Irregularity of a Graph PDF PostScript
Hosam Abdo, Stephan Brandt, Darko Dimitrov 201-206
The Price of Connectivity for Vertex Cover PDF PostScript
Eglantine Camby, Jean Cardinal, Samuel Fiorini, Oliver Schaudt 207-224
On the Cartesian product of of an arbitrarily partitionable graph and a traceable graph PDF PostScript
Olivier Baudon, Julien Bensmail, Rafał Kalinowski, Antoni Marczyk, Jakub Przybyło, Mariusz Woźniak 225-232

ISSN: 1365-8050