Characterizations of naturally submodular graphs: a polynomially solvable class of the TSP
HTML articles powered by AMS MathViewer
- by Yale T. Herer and Michal Penn PDF
- Proc. Amer. Math. Soc. 123 (1995), 673-679 Request permission
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
- S. Anily and A. Federgruen, One warehouse multiple retailer systems with vehicle routing costs, Management Sci. 36 (1990), no. 1, 92–114. MR 1038217, DOI 10.1287/mnsc.36.1.92
- J. A. Bondy and U. S. R. Murty, Graph theory with applications, American Elsevier Publishing Co., Inc., New York, 1976. MR 0411988, DOI 10.1007/978-1-349-03521-2
- Gérard Cornuéjols, Jean Fonlupt, and Denis Naddef, The traveling salesman problem on a graph and some related integer polyhedra, Math. Programming 33 (1985), no. 1, 1–27. MR 809746, DOI 10.1007/BF01582008
- A. Federgruen, M. Queyranne, and Yu-Sheng 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), no. 4, 951–963. MR 1196404, DOI 10.1287/moor.17.4.951 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. Y. Herer, Submodularity and the Traveling Salesman Problem, Tech. Report No. 915, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY, 1990. 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.
- Robin O. Roundy, Computing nested reorder intervals for multi-item distribution systems, Oper. Res. 38 (1990), no. 1, 37–52. MR 1041231, DOI 10.1287/opre.38.1.37 C. Kuratowski, Sur le probleme des courbes gauches en topologie, Fund. Math. 15 (1930), 271-283.
- E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys (eds.), The traveling salesman problem, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1985. A guided tour of combinatorial optimization; A Wiley-Interscience Publication. MR 811467
- Sandra L. Mitchell, Linear algorithms to recognize outerplanar and maximal outerplanar graphs, Inform. Process. Lett. 9 (1979), no. 5, 229–232. MR 552536, DOI 10.1016/0020-0190(79)90075-9 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.
- Robin Roundy, A 98%-effective lot-sizing rule for a multiproduct, multistage production/inventory system, Math. Oper. Res. 11 (1986), no. 4, 699–727. MR 865565, DOI 10.1287/moor.11.4.699
- Robert Tarjan, Depth-first search and linear graph algorithms, SIAM J. Comput. 1 (1972), no. 2, 146–160. MR 304178, DOI 10.1137/0201010
Additional Information
- © Copyright 1995 American Mathematical Society
- 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