The facets of the subtour polytope

Discrete Optimization 2026 Open access

Read full text
Authors: Brahim Chaourar
DOI: 10.1016/j.disopt.2026.100929
Cited by: 0
References: 5

Abstract

Let $G=(V, E)$ be an undirected graph. An independent result of Maurras \cite{Maurras 1975}, and Gr\"{o}tschel and Padberg \cite{Grotschel and Padberg 1979b} gives a characterization of the facets of the subtour polytope when $G$ is complete. In this paper, we generalize this result to arbitrary graphs.

Fields of Study & Subjects

Complexity and Algorithms in Graphs Vehicle Routing Optimization Methods Advanced Graph Theory Research

Publication details

Journal / source
Discrete Optimization
Volume
59
Pages
100929–100929
Publication date
12 January 2026
Language
EN