On a directed tree problem motivated by a newly introduced graph product
<div class="page" title="Page 1"><div class="layoutArea"><div class="column"><p><span style="font-size: 9.000000pt; font-family: 'CMR9';">In this paper we introduce and study a directed tree problem motivated b...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia
2015-10-01
|
| Series: | Electronic Journal of Graph Theory and Applications |
| Subjects: | |
| Online Access: | https://www.ejgta.org/index.php/ejgta/article/view/147 |
| _version_ | 1818531875869687808 |
|---|---|
| author | Antoon H. Boode Hajo Broersma Jan F. Broenink |
| author_facet | Antoon H. Boode Hajo Broersma Jan F. Broenink |
| author_sort | Antoon H. Boode |
| collection | DOAJ |
| description | <div class="page" title="Page 1"><div class="layoutArea"><div class="column"><p><span style="font-size: 9.000000pt; font-family: 'CMR9';">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. </span></p></div></div></div> |
| first_indexed | 2024-12-11T17:38:10Z |
| format | Article |
| id | doaj.art-096aa3644df545f6b9fabf0b164a18bc |
| institution | Directory Open Access Journal |
| issn | 2338-2287 |
| language | English |
| last_indexed | 2024-12-11T17:38:10Z |
| publishDate | 2015-10-01 |
| publisher | Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia |
| record_format | Article |
| series | Electronic Journal of Graph Theory and Applications |
| spelling | doaj.art-096aa3644df545f6b9fabf0b164a18bc2022-12-22T00:56:36ZengIndonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), IndonesiaElectronic Journal of Graph Theory and Applications2338-22872015-10-013210.5614/ejgta.2015.3.2.548On a directed tree problem motivated by a newly introduced graph productAntoon H. Boode0Hajo Broersma1Jan F. Broenink2Robotics and Mechatronics, Faculty EEMCS, University of Twente The NetherlandsFormal Methods and Tools, Faculty EEMCS, University of Twente The NetherlandsDepartment of Computer Engineering, InHolland University of Applied Science The Netherlands<div class="page" title="Page 1"><div class="layoutArea"><div class="column"><p><span style="font-size: 9.000000pt; font-family: 'CMR9';">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. </span></p></div></div></div>https://www.ejgta.org/index.php/ejgta/article/view/147finite deterministic directed acyclic labelled multi-graphs, vertex removing synchronised graph product, target trees, periodic real-time systems |
| spellingShingle | Antoon H. Boode Hajo Broersma Jan F. Broenink On a directed tree problem motivated by a newly introduced graph product Electronic Journal of Graph Theory and Applications finite deterministic directed acyclic labelled multi-graphs, vertex removing synchronised graph product, target trees, periodic real-time systems |
| title | On a directed tree problem motivated by a newly introduced graph product |
| title_full | On a directed tree problem motivated by a newly introduced graph product |
| title_fullStr | On a directed tree problem motivated by a newly introduced graph product |
| title_full_unstemmed | On a directed tree problem motivated by a newly introduced graph product |
| title_short | On a directed tree problem motivated by a newly introduced graph product |
| title_sort | on a directed tree problem motivated by a newly introduced graph product |
| topic | finite deterministic directed acyclic labelled multi-graphs, vertex removing synchronised graph product, target trees, periodic real-time systems |
| url | https://www.ejgta.org/index.php/ejgta/article/view/147 |
| work_keys_str_mv | AT antoonhboode onadirectedtreeproblemmotivatedbyanewlyintroducedgraphproduct AT hajobroersma onadirectedtreeproblemmotivatedbyanewlyintroducedgraphproduct AT janfbroenink onadirectedtreeproblemmotivatedbyanewlyintroducedgraphproduct |