On a directed tree problem motivated by a newly introduced graph product

Antoon H. Boode (Robotics and Mechatronics, Faculty EEMCS, University of Twente The Netherlands)
Hajo Broersma (Formal Methods and Tools, Faculty EEMCS, University of Twente The Netherlands)
Jan F. Broenink (Department of Computer Engineering, InHolland University of Applied Science The Netherlands)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 3, No 2 (2015): Electronic Journal of Graph Theory and Applications

In this paper we introduce and study a directed tree problem motivated by a new graph product that we have recently introduced and analysed in two conference contributions in the context of periodic real-time processes. While the two conference papers were focussing more on the applications, here we mainly deal with the graph theoretical and computational complexity issues. We show that the directed tree problem is NP-complete and present and compare several heuristics for this problem.