# zbMATH — the first resource for mathematics

Computation of inverse 1-center location problem on the weighted trapezoid graphs. (English) Zbl 1452.05077
Summary: Let $$T_{TRP}$$ be the tree corresponding to the weighted trapezoid graph $$G=(V,E)$$. The eccentricity $$e(v)$$ of the vertex $$v$$ is defined as the sum of the weights of the vertices from $$v$$ to the vertex farthest from $$v \in T_{TRP}$$. A vertex with minimum eccentricity in the tree $$T_{TRP}$$ is called the 1-center of that tree. In an inverse 1-center location problem, the parameter of the tree $$T_{TRP}$$ corresponding to the weighted trapezoid graph $$G=(V,E)$$, like vertex weights, have to be modified at minimum total cost such that a pre-specified vertex $$s\in V$$ becomes the 1-center of the trapezoid graph $$G$$. In this paper, we present an optimal algorithm to find an inverse 1-center location on the weighted tree $$T_{TRP}$$ corresponding to the weighted trapezoid graph $$G=(V,E)$$, where the vertex weights can be changed within certain bounds. The time complexity of our proposed algorithm is $$O(n)$$, where $$n$$ is the number of vertices of the trapezoid graph $$G$$.
##### MSC:
 05C22 Signed and weighted graphs 05C85 Graph algorithms (graph-theoretic aspects) 05C05 Trees 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
##### Software:
 [1] B. Alizadeh and R. E. Burkard, Inverse 1-center location problems with edge length augmentation on tree, Computing, 86 (2009), 331-343. · Zbl 1180.90163 [2] B. Alizadeh and R. E. Burkard, Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees, Networks, 58 (2011), 190-200. · Zbl 1236.90094 [3] S. C. Barman, S. Mondal, and M. Pal, A linear time algorithm to construct a tree 4-spanner on trapezoid graphs, International Journal of Computer Mathematics, 87 (2008), 1-13. · Zbl 1209.05236 [4] R. E. Burkard, C. Pleschiutschnig, and J. Zhang, Inverse median problems, Discrete Optimization, 1 (2004), 23-39. · Zbl 1087.90038 [5] R. E. Burkard, C. Pleschiutschnig, and J. Zhang, The inverse 1-median problem on a cycle, Discrete Optimization, 16 (2007), 50-67. · Zbl 1177.90245 [6] R. E. Burkard, M. Galavii, and E. Gassner, The inverse Fermal-Weber problem, Technical Report 2008-14, Graz University of Technology, Graz, 2008. · Zbl 1188.90209 [7] R. E. Burkard and B. Alizadeh, Inverse center location problems, International Symposium on Combinatorial Optimization, 36 (2010), 105-110. · Zbl 1237.90190 [8] D. Burton and Ph. L. Toint, On an instance of the inverse shortest paths problem, Math. Programming, 53 (1992), 45-61. · Zbl 0756.90089 [9] M. C. Cai and Y. J. Li, Inverse matroid intersection problem, ZOR Math. Meth. Oper. Res., 45 (1997), 235-243. · Zbl 0882.90107 [10] M. C. Cai, X. G. Yang, and J. Z. Zhang, The complex analysis of the inverse center location problem, Journal of Global Optimization, 15 (1999), 213-218. · Zbl 0978.90065 [11] D. G. Corneil and P. A. Kamula, Extension of permutation and interval graphs, Congressus Numerantium, 58 (1987), 267-275. · Zbl 0652.05055 [12] I. Dagan, M. C. Golumbic, and R. Y. Pinter, Trapezoid graphs and their coloring, Discrete Applied Mathematics, 21 (1988), 35-46. · Zbl 0658.05067 [13] M. S. Daskin, Network and Discrete Location: Models, Algorithms, and Applications, Wiley, New York, 1995. · Zbl 0870.90076 [14] R. B. Dial, Minimal-revenue congestion pricing part-I: A fast algorithm for the single-origin case, Transportation Res. Part B, 33 (1999), 189-202. [15] Z. Drezner and H. W. Hamacher, Facility Location, Applications and Theory, Springer, Berlin, 2004. · Zbl 0988.00044 [16] C. W. Duin and A. Volgenant, Some inverse optimization problems under the Hamming distance, European Journal of Operational Research, 170 (2006), 887-899. · Zbl 1091.90065 [17] H. W. Engl, M. Hanke, and A. Neubauer, Regularization of Inverse Problems, Kluwer Academic Publishers Group, Dordrecht, 1996. · Zbl 0859.65054 [18] R. L. Francis, L. F. McGinnis, and J. A. White, Facility Layout and Location, An Analytical Approach, Prentice Hall, Englewood Cliffs, 1992. [19] M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 2004. · Zbl 1050.05002 [20] M. Galavi, Inverse 1-median problems, Ph. D. thesis, Institue of Optimization and Discrete Mathematics, Graz University of Technology, Graz, 2008. [21] E. Gassner, The inverse 1-maxian problem with edge length modification, J. Combinatorial Optimization, 16 (2007), 50-67. · Zbl 1180.90165 [22] E. Gassner, An inverse approach to convex ordered median problems in trees, Technical Report 2008-16, Graz University of Technology, Graz, 2008. · Zbl 1243.90223 [23] X. Guan and J. Zhang, Inverse bottleneck optimization problems under weighted Hamming Distance, Lecture Notes in Computer Science, 4041 (2006), 220-230. · Zbl 1137.90691 [24] A. Hashimoto and J. Stevens, Wire routing by optimizing channel assignment within large apertures, in Proc. 8th IEEE Design Automation Workshop, (1971), 155-169. [25] C. Heuberger, Inverse combinatorial optimization: A survey on problems, methods, and results, Journal of Combinatorial Optimization, 8 (2004), 329-361. · Zbl 1084.90035 [26] B. Jana, S. Mondal, and M. Pal, Computation of inverse 1-center location problem on the weighted trees, CiiT International Journal of Networking and Communication Engineering, 4 (2012), 70-75. [27] B. Jana, S. Mondal, and M. Pal, Computation of inverse 1-center location problem on the weighted interval graphs, Int. J. Computing Science and Mathematics, 8 (2017), 533-541. [28] H. Kellerer, U. Pferschy, and D. Pisinger, Knapsack Problems, Springer, Berlin, 2004. [29] Y. D. Liang, Domination in trapezoid graphs, Information Processing Letters, 52 (1994), 309-315. · Zbl 0938.68925 [30] T. Ma, and J. P. Spinrad, An $$O(n^2)$$ algorithm for $$2$$-chain problem on certain classes of perfect graphs, in Proc. 2nd ACM-SIAM Symp. on Discrete Algorithms, 1991. · Zbl 0800.68606 [31] B. Marlow and N. Megiddo, Inverse problems and linear-time algorithms for linear programming in R3 and related problems, SIAM J. Comput., 12 (1983), 759-776. · Zbl 0521.68034 [32] B. P. Mirchandani and R. L. Francis, Discrete Location Theory, Wiley, New York, 1990. · Zbl 0718.00021 [33] S. Mondal, M. Pal, and T. K. Pal, An optimal algorithm for solving all-pairs shortest paths on trapezoid graphs, Intern. J. Comput. Engg. Sci., 3.2 (2002), 103-116. [34] T. J. Moser, Shortest paths calculation of seismic rays, Geophysics, 56 (1991), 59-67. [35] S. Nickel, and J. Puerto, Location Theory, A Unified Approach, Springer, Berlin, 2005. · Zbl 1229.90001 [36] A. Saha, M. Pal, and T. K. Pal, Selection of program slots of television channels for giving advertisement: A graph theoretic approach, Information Sciences, 177.12 (2007), 2480-2492. · Zbl 1115.05087 [37] R. E. Tarjan, Depth first search and linear graph algorithm, SIAM J. Comput., 2 (1972), 146-160. · Zbl 0251.05107 [38] C. Yang and J. Z. Zhang, Two general methods for inverse optimization problems, Appl. Math. Lett., 12 (1999), 69-72. · Zbl 0935.90023 [39] X. Yang and J. Zhang, Inverse center location problem on a tree, Journal of Systems Science and Complexity, 21 (2008), 651-664. · Zbl 1180.90171 [40] J. Z. Zhang and Z. H. Liu, Calculating some inverse linear programming problems, J. Computational and Applied Mathematics, 72 (1996), 261-273. · Zbl 0856.65069 [41] J. · Zbl 0866.90099