print page

Volker Turau

Picture of Volker Turau
Prof. Dr. rer. nat. Volker Turau
Room 4.088, building E
Am Schwarzenberg-Campus 3
21073 Hamburg
phone+49 40 42878 - 3530
fax+49 40 427 - 3 - 10456
e-mail

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 3.

Teaching

Publications

Florian Meyer, Ivonne Andrea Mantilla-Gonzales and Volker Turau. New CAP Reduction Mechanisms for IEEE 802.15.4 DSME to SupportFluctuating Traffic in IoT Systems. In Proceedings of 19th International Conference on Ad Hoc Networks and Wireless (AdHoc-Now 2020), Springer, October 2020, pp. 159–179. Bari, Italy / Virtually.
@InProceedings{Telematik_adhocnow_2020, author = {Florian Meyer and Ivonne Andrea Mantilla-Gonzales and Volker Turau}, title = {New CAP Reduction Mechanisms for IEEE 802.15.4 DSME to SupportFluctuating Traffic in IoT Systems}, booktitle = {Proceedings of 19th International Conference on Ad Hoc Networks and Wireless (AdHoc-Now 2020)}, pages = {159-179}, publisher = {Springer}, day = {19-21}, month = oct, year = 2020, location = {Bari, Italy / Virtually}, }
Abstract: In 2015, the IEEE 802.15.4 standard was expanded by theDeterministic and Synchronous Multi-Channel Extension (DSME) toincrease reliability, scalability and energy-efficiency in industrial appli-cations. The extension offers a TDMA/FDMA-based channel access,where time is divided into two alternating phases, a contention accessperiod (CAP) and a contention free period (CFP). During the CAP, transmission slots can be allocated offering an exclusive access to theshared medium during the CFP. The fractionτof CFP’s time slots ina dataframe is a critical value, because it directly influences agility andthroughput. A high throughput demands that the CFP is much longerthan the CAP, i.e., a high value ofτ, because application data is only sentduring the CFP. High agility is given if the expected waiting time to senda CAP message is short and that the length of the CAPs are long enoughto accommodate necessary GTS negotiations, i.e., a low value ofτ. OnceDSME is configured according to the needs of an application,τcan onlyassume one of two values and cannot be changed at run-time. In thispaper, we propose two extensions of DSME that allow to adoptτto thecurrent traffic pattern. We show theoretically and through simulationsthat the proposed extensions provide a high degree of responsiveness totraffic fluctuations while keeping the throughput high.
Volker Turau. A Distributed Algorithm for Finding Hamiltonian Cycles in Random Graphs in O(logn) Time. Theoretical Computer Science, September 2020.
@Article{Theoretical computer science__2020, author = {Volker Turau}, title = {A Distributed Algorithm for Finding Hamiltonian Cycles in Random Graphs in O(logn) Time}, pages = , journal = {Theoretical Computer Science}, publisher = {Elsevier}, month = sep, year = 2020, }
Abstract: It is known for some time that a random graph G(n,p) contains w.h.p. a Hamiltonian cycle if p is larger than the critical value pcrit = (logn + log log n+ωn)/n. The determination of a concrete Hamiltonian 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(logn) rounds. The algorithm works in the synchronous model and usesmessages of size O(logn) and O(logn) memory per node.
Volker Turau. Stateless Information Dissemination Algorithms. In Structural Information and Communication Complexity - 27th International Colloquium, SIROCCO 2020, Springer, June 2020, pp. 183–199.
@InProceedings{Telematik_sirocco_2020, author = {Volker Turau}, title = {Stateless Information Dissemination Algorithms}, booktitle = {Structural Information and Communication Complexity - 27th International Colloquium, SIROCCO 2020}, pages = {183-199}, publisher = {Springer}, day = {29-1}, month = jun, year = 2020, location = {}, }
Abstract: Stateless protocols are advantageous in high volume applications, increasing performance by removing the load caused by retention of session information and by providing crash tolerance. In this paper we present an optimal stateless information dissemination algorithm for synchronous distributed systems. The termination time is considerable lower than that of a recently proposed stateless dissemination protocol. Apart from a special case the new algorithm achieves the minimum possible termination time. The problem of selecting k dissemination nodes with minimal termination time is NP-hard. We prove that unless NP = P there is no approximation algorithm for this problem with approximation ratio 3/2−ϵ. We also prove for asynchronous systems that deterministic stateless information dissemination is only possible if a large enough part of the message can be updated by each node.

The complete list of publications is available separately.

Supervised Theses

Ongoing Theses

Completed Theses