Achieving Feasibility for Clustered TSP using Intersection Graphs

Authors

DOI:

https://doi.org/10.7155/jgaa.v30i1.3172

Keywords:

Clustered Travelling Salesman Problem, Feasibility, Optimization, Intersection graphs

Abstract

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

Download data is not yet available.

Downloads

Published

2026-11-22

How to Cite

Guttmann-Beck, N., Meshita-Sayag, H., & Stern, M. (2026). Achieving Feasibility for Clustered TSP using Intersection Graphs. Journal of Graph Algorithms and Applications, 30(1), 517–541. https://doi.org/10.7155/jgaa.v30i1.3172

Issue

Section

Articles

Categories