The complexity of a minimum reload cost diameter problem |
| |
Authors: | Giulia Galbiati |
| |
Institution: | Università degli Studi di Pavia, Facoltà di Scienze M.F.N.-Dipartimento di Informatica e Sistemistica, Via Ferrata 1, I-27100 Pavia, Italy |
| |
Abstract: | We consider the minimum diameter spanning tree problem under the reload cost model which has been introduced by Wirth and Steffan H.-C. Wirth, J. Steffan, Reload cost problems: Minimum diameter spanning tree, Discrete Appl. Math. 113 (2001) 73-85]. In this model an undirected edge-coloured graph G is given, together with a nonnegative symmetrical integer matrix R specifying the costs of changing from a colour to another one. The reload cost of a path in G arises at its internal nodes, when passing from the colour of one incident edge to the colour of the other. We prove that, unless P=NP, the problem of finding a spanning tree of G having a minimum diameter with respect to reload costs, when restricted to graphs with maximum degree 4, cannot be approximated within any constant α<2 if the reload costs are unrestricted, and cannot be approximated within any constant β<5/3 if the reload costs satisfy the triangle inequality. This solves a problem left open by Wirth and Steffan H.-C. Wirth, J. Steffan, Reload cost problems: minimum diameter spanning tree, Discrete Appl. Math. 113 (2001) 73-85]. |
| |
Keywords: | Reload cost model Combinatorial optimization Minimum diameter spanning tree Approximation algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|