×

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.)
PDF BibTeX XML Cite
Full Text: DOI Euclid
References:
[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.