Characterizations of Natural Submodular Graphs: A Polynomially Solvable Class of the TSP

DOI10.2307/2160785zbMath0826.05048OpenAlexW4250291751MaRDI QIDQ4327639

Yale T. Herer, Michal Penn

Publication date: 10 April 1995

Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2160785

zbMATH Keywords

travelling salesman problemclosed walkSteiner tournaturally submodular graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items (7)

Operations research games: A survey. (With comments and rejoinder) ⋮ On the convexity of independent set games ⋮ Submodularity and the traveling salesman problem ⋮ Naturally submodular digraphs and forbidden digraph configurations ⋮ On the submodularity of multi-depot traveling salesman games ⋮ Clique partitioning of interval graphs with submodular costs on the cliques ⋮ On the properties of weighted minimum colouring games

This page was built for publication: Characterizations of Natural Submodular Graphs: A Polynomially Solvable Class of the TSP