Talk:Ring star problem
Add topic | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||
Confusing and ambiguous
[edit]The description is vague at the moment. And the diagram appears to be a subgraph that is a solution to the ring star problem, with the original graph not being provided. As such, a number of details are unclear:
- Is the cycle made up of undirected edges in the original graph, and the stars made up of directed edges? Or are the ring edges always undirected and the star edges either directed or undirected, as long as they aren't directed away from the ring? Or are edges directed or undirected in free combination, as long as the ring is a cycle per any edge directions it has and the star edges are directed (if at all) towards the ring?
- What is the significance of one or more nodes being designated as depots? Are the depots specified in the original graph, with a requirement that at least one of these be on the ring?
- The description seems to be using "parent node" to mean the 'to' node of an edge, and "child node" to mean the 'from' node. Is this indeed the case? Whilst it may make sense in terms of the hierarchy of the solved ring-star structure, in terms of the directions of the arrows it is counterintuitive and hence confusing.
This source describes the problem as starting with a complete mixed graph – apparently this means every pair of nodes has three connections: one undirected edge ("edge" in the paper) and a directed edge ("arc") in each direction, and the three can all have different costs ("routing cost" for the undirected edge and "assignment cost" for the arcs). If this is what "complete (weighted) mixed graph" indeed means, this isn't clear from the description here. And do we take the position that a weight can be infinite, meaning no direct path exists between two places?
So by this formulation, a subgraph is being constructed using the undirected edges for the ring and the arcs for the stars. I'm puzzled as to why the problem is designed such that costs along the ring have to be direction-independent but costs on stars can be direction-dependent.
And there is a problem in that this source doesn't seem to address the scenario of multiple depots. Can anyone shed light? Moreover, would anyone like to help to make the description here clearer and more complete generally? — Smjg (talk) 12:03, 30 May 2026 (UTC)