{
  "id": "enwiki-001369802225",
  "slug": "ring-star-problem",
  "title": "Ring star problem",
  "qid": "",
  "lead": "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.",
  "body": "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.",
  "categories": [
    "113062478",
    "22902725",
    "22944369",
    "23057298",
    "23603337",
    "26220375",
    "28174277"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1369802225",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1786943379.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001369802225",
    "type": "webpage",
    "title": "Ring star problem",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/ring-star-problem",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          15
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          15
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001369802225",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1369802225",
    "note": "Immutable snapshot enwiki-001369802225"
  }
}