Title of article
On a directed tree problem motivated by a newly introduced graph product
Author/Authors
Boode, Antoon H. University of Twente - Faculty EEMCS, Netherlands , Boode, Antoon H. InHolland University of Applied Science - Department of Computer Engineering, Netherlands , Broersma, Hajo University of Twente - Faculty EEMCS, Netherlands , Broenink, Jan F. University of Twente - Faculty EEMCS, Netherlands
From page
162
To page
181
Abstract
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.
Keywords
finite deterministic directed acyclic labelled multi , graphs , vertex removing synchronised graph product , target trees , periodic real , time systems
Journal title
Electronic Journal of Graph Theory and Applications (EJGTA)
Journal title
Electronic Journal of Graph Theory and Applications (EJGTA)
Record number
2621249
Link To Document