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
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, Phil Malessa, Jan Diercks and Volker Turau. Are Group Acknowledgements Worth Anything in IEEE 802.15.4 DSME: A Comparative Analysis. In Accepted for Publication in Proceedings of 5th International Conference on Cloud and Internet of Things, CIoT '22, IEEE, March 2022. Marrakesh, Morocco.
@InProceedings{Telematik_CIoT_2021, author = {Florian Meyer and Phil Malessa and Jan Diercks and Volker Turau}, title = {Are Group Acknowledgements Worth Anything in IEEE 802.15.4 DSME: A Comparative Analysis}, booktitle = {Accepted for Publication in Proceedings of 5th International Conference on Cloud and Internet of Things, CIoT '22}, pages = , publisher = {IEEE}, day = {28-30}, month = mar, year = 2022, location = {Marrakesh, Morocco}, }
Volker Turau. Fixed Points and 2-Cycles of Synchronous Dynamic Coloring Processes on Trees. In Proceedings of 29th International Colloquium on Structural Information and Communication Complexity - Sirocco 2022 -, Springer, June 2022, pp. 265–282. Paderborn, Germany.
@InProceedings{Telematik_sirocco_2022, author = {Volker Turau}, title = {Fixed Points and 2-Cycles of Synchronous Dynamic Coloring Processes on Trees}, booktitle = {Proceedings of 29th International Colloquium on Structural Information and Communication Complexity - Sirocco 2022 -}, pages = {265-282}, publisher = {Springer}, day = {27-29}, month = jun, year = 2022, location = {Paderborn, Germany}, }
Abstract: This paper considers synchronous discrete-time dynamical systems on graphs based on the threshold model. It is well known that after a finite number of rounds these systems either reach a fixed point or enter a 2-cycle. The problem of finding the fixed points for this type of dynamical system is in general both NP-hard and #P-complete. In this paper we give a surprisingly simple graph-theoretic characterization of fixed points and 2-cycles for the class of finite trees. Thus, the class of trees is the first nontrivial graph class for which a complete characterization of fixed points exists. This characterization enables us to provide bounds for the total number of fixed points and pure 2-cycles. It also leads to an output-sensitive algorithm to efficiently generate these states.
Volker Turau. Fixed Points and 2-Cycles of Synchronous Dynamic Coloring Processes on Trees. Technical Report Report arXiv 2202.01580, arXiv.org e-Print Archive - Computing Research Repository (CoRR), Cornell University, February 2022.
@TechReport{CoRR 2022, author = {Volker Turau}, title = {Fixed Points and 2-Cycles of Synchronous Dynamic Coloring Processes on Trees}, number = {Report arXiv 2202.01580}, institution = {arXiv.org e-Print Archive - Computing Research Repository (CoRR)}, address = {Cornell University}, month = feb, year = 2022, }
Abstract: This paper considers synchronous discrete-time dynamical systems on graphs based on the threshold model. It is well known that after a finite number of rounds these systems either reach a fixed point or enter a 2-cycle. The problem of finding the fixed points for this type of dynamical system is in general both NP-hard and #P-complete. In this paper we give a surprisingly simple graph-theoretic characterization of fixed points and 2-cycles for the class of finite trees. Thus, the class of trees is the first nontrivial graph class for which a complete characterization of fixed points exists. This characterization enables us to provide bounds for the total number of fixed points and pure 2-cycles. It also leads to an output-sensitive algorithm to efficiently generate these states.

The complete list of publications is available separately.

Supervised Theses

Ongoing Theses

Completed Theses