Volker Turau
Prof. Dr. rer. nat. Volker Turau
Room 4.088, building E
Am Schwarzenberg-Campus 3
21073 Hamburg
Am Schwarzenberg-Campus 3
21073 Hamburg
+49 40 42878 - 3530
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)
De Gruyter Studium, 2015, ISBN 978-3-110-41727-2 (Solutions)
Erdős number
My Erdős number is 3.
Teaching
- Distributed Algorithms
- Distributed Systems
- Operating Systems
- Randomised Algorithms and Random Graphs
- Software for Embedded Systems
- Akustische Anwendungen in Drahtlosen Sensornetzen
- Intelligente Stromnetze: Kommunikation, Regelung, Sicherheit und Privatsphäre
- MAC Protocols in the Industrial Internet of Things
- Nebenläufige Programmierung von Multicore-Systemen
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.