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

    Research output: Contribution to journalArticleAcademicpeer-review

    55 Downloads (Pure)

    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.
    Original languageUndefined
    Pages (from-to)162-181
    Number of pages20
    JournalElectronic journal of graph theory and applications
    Volume3
    Issue number2
    DOIs
    Publication statusPublished - 21 Oct 2015

    Keywords

    • target trees
    • vertex removing synchronised graph product
    • EWI-26386
    • IR-97863
    • periodic real-time systems
    • finite deterministic directed acyclic labelled multi-graphs
    • METIS-312744
    • CR-G.2.2

    Cite this