Ring star problem
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
The ring star problem (RSP) is a NP-hard problem 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 from the cycle's costs. The cycle must contain at least one node designated as the depot or the root. RSP is a generalization of the traveling salesman problem. 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, transports or logistics.
The ring star problem (RSP) is a NP-hard problem 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 from the cycle's costs. The cycle must contain at least one node designated as the depot or the root. RSP is a generalization of the traveling salesman problem. 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, transports or logistics.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1369802225 under CC BY-SA 4.0; modifications have been made.