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
StatePublished - 21 Oct 2015

Fingerprint

Computational complexity

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

@article{31cd3d8f3a204964b6385e58e0afdf0a,
title = "On a directed tree problem motivated by a newly introduced graph product",
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 = "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",
author = "Boode, {Antoon Hendrik} and Broersma, {Haitze J.} and Broenink, {Johannes F.}",
note = "eemcs-eprint-26386",
year = "2015",
month = "10",
doi = "10.5614/ejgta.2015.3.2.5",
volume = "3",
pages = "162--181",
journal = "Electronic journal of graph theory and applications",
issn = "2338-2287",
publisher = "Indonesian Combinatorics Society",
number = "2",

}

TY - JOUR

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

AU - Boode,Antoon Hendrik

AU - Broersma,Haitze J.

AU - Broenink,Johannes F.

N1 - eemcs-eprint-26386

PY - 2015/10/21

Y1 - 2015/10/21

N2 - 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.

AB - 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.

KW - target trees

KW - vertex removing synchronised graph product

KW - EWI-26386

KW - IR-97863

KW - periodic real-time systems

KW - finite deterministic directed acyclic labelled multi-graphs

KW - METIS-312744

KW - CR-G.2.2

U2 - 10.5614/ejgta.2015.3.2.5

DO - 10.5614/ejgta.2015.3.2.5

M3 - Article

VL - 3

SP - 162

EP - 181

JO - Electronic journal of graph theory and applications

T2 - Electronic journal of graph theory and applications

JF - Electronic journal of graph theory and applications

SN - 2338-2287

IS - 2

ER -