The ring star problem (RSP) is a NP-hard problem[1] in combinatorial optimization. In a complete weighted mixed graph, the ring star problem aims to find a minimum cost ring star subgraph formed by a cycle (ring part) and a set of arcs (star part) such that each arc's child node belongs to the cycle and each arc's parent node does not. The costs for the arcs are usually different than the cycle's costs. The cycle must contains at least one node which is called the depot or the root.
RSP is a generalization of the traveling salesman problem.[1] When the costs of the arcs are infinite and the ring contains all nodes, the RSP reduces to TSP. Some applications of RSP arise in the context of telecommunications,[2] transports or logistics.
- ^ a b Labbé, Martine; Laporte, Gilbert; Martín, Inmaculada Rodríguez; González, Juan José Salazar (May 2004). "The Ring Star Problem: Polyhedral analysis and exact algorithm". Networks. 43 (3): 177–189. doi:10.1002/net.10114. ISSN 0028-3045.
- ^ Cite error: The named reference
Xu1998was invoked but never defined (see the help page).