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
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?)

  • [AF90] S. Anily and A. Federgruen, One warehouse multiple retailer systems with vehicle routing costs, Management Sci. 36 (1990), 92-114. MR 1038217 (90m:90100)
  • [BM76] J. A. Bondy and U. S. R. Murty, Graph theory with application, Elsevier Science, New York, 1976. MR 0411988 (54:117)
  • [CFN85] G. Cornuéjols, J. Fonlupt, and D. Naddef, The Traveling Salesman Problem on a graph and some related polyhedra, Math. Programming 33 (1985), 1-27. MR 809746 (87c:90074)
  • [FZQ92] A. Federgruen, M. Queyranne, and Y. S. Zheng, Simple power of two policies are close to optimal in a general class of production/distribution networks with general joint setup costs, Math. Oper. Res. 17 (1992), 951-963. MR 1196404 (93j:90045)
  • [FZ88] A. Federgruen and Y. S. Zheng, Minimizing submodular set functions: Efficient algorithms for special structures with applications to joint replenishment problems, Working Paper, Wharton School, University of Pennsylvania, Philadelphia, 1988.
  • [H90] Y. Herer, Submodularity and the Traveling Salesman Problem, Tech. Report No. 915, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY, 1990.
  • [HP93] Y. Herer and M. Penn, Characterizations of naturally submodular graphs: motivational and algorithmic aspects, Operations Research Statistics and Economics Mimeograph Series No. 407, Industrial Engineering and Management, Technion--Israel Institute of Technology, Haifa, Israel, 1993.
  • [HR90] Y. Herer and R. Roundy, Heuristics for a one warehouse multi-retailer distribution problem with performance bounds, Oper. Res. (to appear). MR 1041231 (90m:90108)
  • [K30] C. Kuratowski, Sur le probleme des courbes gauches en topologie, Fund. Math. 15 (1930), 271-283.
  • [LLRS85] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys (eds.), The Traveling Salesman Problem, a guided tour of combinatorial optimization, Wiley, Chichester, 1985. MR 811467 (87f:90057)
  • [M79] S. L. Mitchell, Linear algorithms to recognize outerplanar and maximal outerplanar graphs, Inform. Process. Lett. 9 (1979), 229-232. MR 552536 (80k:68052)
  • [Q85] M. Queyranne, A polynomial-time submodular extension to Roundy's 98%-effective heuristic for production/inventory systems, Working Paper No. 1135, Faculty of Commerce and Business Administration, University of British Columbia, Vancouver, 1985.
  • [R86] R. Roundy, A 98%-effective lot-sizing rule for a multi-product, multi-stage production/ inventory system, Math. Oper. Res. 11 (1986), 699-727. MR 865565 (87i:90086)
  • [T2] R. Tarjan, Depth-first search and linear graph algorithms, SIAM J. Comput. 1 (1972), 146-160. MR 0304178 (46:3313)

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

Keywords: Submodular functions, traveling salesman problem, graphs, algorithms
Article copyright: © Copyright 1995 American Mathematical Society

American Mathematical Society