Discrete Mathematics & Theoretical Computer Science

In 2015 DMTCS will migrate to http://dmtcs.episciences.org/ on the Episciences platform:

  • All open submissions will continued on the server where they were first submitted.
  • All existing volumes will be migrated to the new platform.
  • This server here will eventually be discontinued.

Warning: Due to massif spamming of our user database, it is not possible to create new user ids via our web interface for this server here. Since we are now in the process of migrating to the new server infrastructure, the easiest would be to switch to that server (see above) and submit to there. If you still want to do a submission to DMTCS on this server here and do not yet have a user id here, please contact us directly by mail and we will create it for you.

The current volume of DMTCS is

  • 17:1, regular issue, publication ongoing.


  • 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 17, No 1 (2015)

Table of Contents

Analysis of Algorithms

How often should you clean your room? PDF PostScript
Kimball Martin, Krishnan Shankar 415-444

Automata, Logic and Semantics

Parameterized Complexity of Synchronization and Road Coloring PDF PostScript
Vojtěch Vorel, Adam Roman 283-306
A Note on a Recent Attempt to Improve the Pin-Frankl Bound PDF
François Gonze, Raphaël M. Jungers, Avraham N. Trahtman 307-308
On the Hausdorff measure of regular ω-languages in Cantor space PDF PostScript
Ludwig Staiger 357-368


Classification of skew translation generalized quadrangles, I PDF PostScript
Koen Thas 89-96
Bootstrapping and double-exponential limit laws PDF PostScript
Helmut Prodinger, Stephan Wagner 123-144
Avoider-Enforcer star games PDF PostScript
Andrzej Grzesik, Mirjana Mikalacki, Zoltan Lorant Nagy, Alon Naor, Balazs Patkos, Fiona Skerman 145-160
Intervals and factors in the Bruhat order PDF PostScript
Bridget Eileen Tenner 383-396

Discrete Algorithms

A randomized algorithm for finding a maximum clique in the visibility graph of a simple polygon PDF PostScript
Sergio Cabello, Maria Saumell 1-12
Cost-effectiveness of algorithms PDF PostScript
Graham Farr 201-218
Output sensitive algorithm for covering many points PDF
Hossein Ghasemalizadeh, Mohammadreza Razzazi 309-316
On substitution tilings of the plane with n-fold rotational symmetry PDF
Gregory Ross Maloney 397-414

Distributed Computing and Networking

An Efficient Certificateless Aggregate Signature Scheme for Vehicular Ad-Hoc Networks PDF
Avleen Kaur Malhi, Shalini Batra 317-338

Graph Theory

Ore-degree threshold for the square of a Hamiltonian cycle PDF
Louis DeBiasio, Safi Faizullah, Imdadullah Khan 13-32
An Approximability-related Parameter on Graphs - Properties and Applications PDF PostScript
Robert Engström, Tommy Färnqvist, Peter Jonsson, Johan Thapper 33-66
On the 1-2-3-conjecture PDF PostScript
Akbar Davoodi, Behnaz Omoomi 67-78
Connectivity of Fibonacci cubes, Lucas cubes, and generalized cubes PDF PostScript
Jernej Azarija, Sandi Klavžar, Jaehun Lee, Yoomi Rho 79-88
Symmetric Bipartite Graphs and Graphs with Loops PDF PostScript
Grant Cairns, Stacey Mendan 97-102
Edge stability in secure graph domination PDF PostScript
Anton Pierre de Villiers, Alewyn Petrus Burger, Jan Harm van Vuuren 103-122
Guarded subgraphs and the domination game PDF PostScript
Boštjan Brešar, Sandi Klavžar, Gasper Košmrlj, Doug F. Rall 161-168
p-Box: A new graph model PDF PostScript
Mauricio Soto, Christopher Thraves Caro 169-186
On probe co-bipartite and probe diamond-free graphs PDF PostScript
Flavia Bonomo, Celina Miraglia Herrera de Figueiredo, Guillermo Alfredo Durán, Luciano Norberto Grippo, Martín Darío Safe, Jayme Luiz Szwarcfiter 187-200
A Conjecture on the Number of Hamiltonian Cycles on Thin Grid Cylinder Graphs PDF PostScript
Olga Bodroza-Pantic, Harris Kwong, Milan Pantic 219-240
Extending a perfect matching to a Hamiltonian cycle PDF PostScript
Adel Alahmadi, Robert E.L. Aldred, Ahmad Alkenani, Rola Hijazi, Patrick Solé, Carsten Thomassen 241-254
Graphs with Large Disjunctive Total Domination Number PDF PostScript
Michael Anthony Henning, Viroshan Naicker 255-282
Maximum difference about the size of optimal identifying codes in graphs differing by one vertex PDF PostScript
Mikko Pelto 339-356
Snarks with total chromatic number 5 PDF
Gunnar Brinkmann, Myriam Preissmann, Diana Sasaki 369-382

ISSN: 1365-8050