Achieving Feasibility for Clustered TSP using Intersection Graphs
DOI:
https://doi.org/10.7155/jgaa.v30i1.3172Keywords:
Clustered Travelling Salesman Problem, Feasibility, Optimization, Intersection graphsAbstract
Let $H = \langle V, \mathcal{S} \rangle $ be a hypergraph, where $V$ is a set of vertices and $\mathcal{S}$ is a set of clusters $S_1,\ldots,S_m$, $S_i \subseteq V$, such that the clusters in $\mathcal{S}$ are not necessarily disjoint.
This paper explores the issue of the Feasibility Clustered Traveling Salesman Problem, which involves determining the existence of a simple path that visits every vertex precisely once, where the vertices contained in each cluster are visited consecutively.
The focus is on hypergraphs without a feasible solution path.
We explore the idea of updating the hypergraph by removing vertices from clusters, such that the resulting hypergraph has a feasible solution path. We use specific structures of the corresponding intersection graph to find the minimum number of vertices that need to be removed, to gain feasibility.
Downloads
Downloads
Published
How to Cite
License
Copyright (c) 2026 Nili Guttmann-Beck, Hadas Meshita-Sayag, Michal Stern

This work is licensed under a Creative Commons Attribution 4.0 International License.


