Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 

 

Characterizations of naturally submodular graphs: a polynomially solvable class of the TSP


Authors: Yale T. Herer and Michal Penn
Journal: Proc. Amer. Math. Soc. 123 (1995), 673-679
MSC: Primary 05C75; Secondary 68Q25, 90C35
DOI: https://doi.org/10.1090/S0002-9939-1995-1260169-4
MathSciNet review: 1260169
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ G = (V,E)$ be a graph and $ w:E \to {R^ + }$ be a length function. Given $ S \subseteq V$, a Steiner tour is a cycle passing at least once through each vertex of S. In this paper we investigate naturally submodular graphs: graphs for which the length function of the Steiner tours is submodular. We provide two characterizations of naturally submodular graphs, an $ O(n)$ time algorithm for identifying such graphs, and an $ O(n)$ time algorithm for solving the Steiner traveling salesman problem on such graphs.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05C75, 68Q25, 90C35

Retrieve articles in all journals with MSC: 05C75, 68Q25, 90C35


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1995-1260169-4
Keywords: Submodular functions, traveling salesman problem, graphs, algorithms
Article copyright: © Copyright 1995 American Mathematical Society