| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4951962 | Theoretical Computer Science | 2017 | 13 Pages |
Abstract
In an edge-colored graph, the cost incurred at a vertex on a path when two incident edges with different colors are traversed is called reload or changeover cost. The Minimum Changeover Cost Arborescence (MinCCA) problem consists in finding an arborescence with a given root vertex such that the total changeover cost of the internal vertices is minimized. It has been recently proved by Gözüpek et al. (2016) that the MinCCA problem when parameterized by the treewidth and the maximum degree of the input graph is in FPT. In this article we present the following hardness results for MinCCA:
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Didem Gözüpek, Sibel Ãzkan, Christophe Paul, Ignasi Sau, Mordechai Shalom,