*[1,2]-domination in generalized Petersen graphs*. Technical Report, 2019.

# Volker Turau

I am professor at Hamburg Universtity of Technology since October 2002.

Program Committee Activities |
Editorial Activities |
CV |
Ph.D. students

## Books

**Algorithmische Graphentheorie**- 4., extended and revised edition

De Gruyter Studium, 2015, ISBN 978-3-110-41727-2 (Solutions)

## Erdős number

My Erdős number is 4.

## Teaching

- Distributed Algorithms
- Distributed Systems
- Operating Systems
- Randomised Algorithms and Random Graphs
- Software for Embedded Systems
- MAC Protocols in the Industrial Internet of Things
- Seminar Smart Grids

## Publications

Fairouz Beggas, Volker Turau, Mohammed Haddad and Hamamache Kheddouci.

@TechReport{Telematik2019,
author = {Fairouz Beggas and Volker Turau and Mohammed Haddad and Hamamache Kheddouci},
title = {[1,2]-domination in generalized Petersen graphs},
pages = ,
journal = {Discrete Mathematics, Algorithms and Applications},
publisher = {World Scientific},
month = ,
year = 2019,
}

Fairouz Beggas, Volker Turau, Mohammed Haddad and Hamamache Kheddouci. [1,2]-domination in generalized Petersen graphs.

*Discrete Mathematics, Algorithms and Applications*, 2019.@Article{Telematik__2019,
author = {Fairouz Beggas and Volker Turau and Mohammed Haddad and Hamamache Kheddouci},
title = {[1,2]-domination in generalized Petersen graphs},
pages = ,
journal = {Discrete Mathematics, Algorithms and Applications},
publisher = {World Scientific},
month = ,
year = 2019,
}

Volker Turau. A Distributed Algorithm for Finding Hamiltonian Cycles in Random Graphs in O(log n) Time. In

*Lecture Notes in Computer Science - Proceedings of 25th International Colloquium on Structural Information and Communication Complexity (Scirocco 2018)*, June 2018, pp. 72–87. Ma'ale HaHamisha, Israel.@InProceedings{Telematik_Scirocco_2018,
author = {Volker Turau},
title = {A Distributed Algorithm for Finding Hamiltonian Cycles in Random Graphs in O(log n) Time},
booktitle = {Lecture Notes in Computer Science - Proceedings of 25th International Colloquium on Structural Information and Communication Complexity (Scirocco 2018)},
pages = {72-87},
day = {18-21},
month = jun,
year = 2018,
location = {Ma'ale HaHamisha, Israel},
}

**Abstract**: It is known for some time that a random graph G(n, p) con- tains w.h.p. a Hamiltonian cycle if p is larger than the critical value pcrit = (log n+log log n+ωn)/n. The determination of a concrete Hamil- tonian cycle is even for values much larger than pcrit a nontrivial task. In this paper we consider random graphs G(n, p) with p in Ω ̃(1/√n), where Ω ̃ hides poly-logarithmic factors in n. For this range of p we present a distributed algorithm AHC that finds w.h.p. a Hamiltonian cycle in O(log n) rounds. The algorithm works in the synchronous model and uses messages of size O(log n) and O(log n) memory per node.

The complete list of publications is available separately.

## Supervised Theses

### Open Theses

- Bestimmung von Dominanzzahlen von Graphen mittels Linearer Programmierung
- Minority Processes in Random Graphs