Abstract
In this paper, the minimum weight vertex covering problem with uncertain vertex weights is investigated. By virtue of the uncertainty distribution operation of independent uncertain variables, the uncertainty distribution of the minimum weight of vertex cover is derived, and the concept of the \(\alpha \)-minimum cover among uncertain weight vertex covers is proposed within the framework of uncertain programming. Then an \(\alpha \)-minimum model for uncertain weight vertex covering problem is established and discussed. Taking advantage of some properties of uncertainty theory, the model can be transformed into the corresponding deterministic form. At last, a numerical example is presented to show the performance of the model.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bar-Yehuda, R., & Even, S. (1981). A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms, 2, 198–203.
Bouamama, S., Blum, C., & Boukerram, A. (2012). A population-based iterated greedy algorithm for the minimum weight vertex cover problem. Applied Soft Computing, 12, 1632–1639.
Feige, U., Hajiaghayi, M. T., & Lee, J. R. (2008). Improved approximation algorithms for minimum weight vertex separators. SIAM Journal on Computing, 38, 629–657.
Gao, X., Gao, Y., & Ralescu, D. A. (2010). On Liu’s inference rule for uncertain systems. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 18, 1–11.
Gao, Y. (2011). Shortest path problem with uncertain arc lengths. Computers & Mathematics with Applications, 62, 2591–2600.
Han, Q., Punnen, A. P., & Ye, Y. (2009). An edge-reduction algorithm for the vertex cover problem. Operations Research Letters, 37, 181–186.
Han, S., Peng, Z., & Wang, S. (2014). The maximum flow problem of uncertain network. Information Sciences, 265, 167–175.
Hartmann, A. K., & Weigt, M. (2001). Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs. Theoretical Computer Science, 265, 199–225.
Kahneman, D., & Tversky, A. (1979). Prospect theory: An analysis of decision under risk. Econometrica, 47, 263–292.
Karp, R. M. (1972). Reducibility among combinatorial problems. In R. E. Miller, J. W. Thatcher, & J. D. Bohlinger (Eds.), Complexity of Computer Computations, 85–103. New York: Plenum Press.
Kovac, P., Rodic, D., Pucovsky, V., Savkovic, B., & Gostimirovic, M. (2013). Application of fuzzy logic and regression analysis for modeling surface roughness in face milliing. Journal of Intelligent Manufacturing, 24, 755–762.
Kratsch, S., & Neumann, F. (2013). Fixed-parameter evolutionary algorithms and the vertex cover problem. Algorithmica, 65, 754–771.
Li, X., & Liu, B. (2009). Hybrid logic and uncertain logic. Journal of Uncertain Systems, 3, 83–94.
Liu, B. (2007). Uncertainty theory (2nd ed.). Berlin: Springer-Verlag.
Liu, B. (2008). Fuzzy process, hybrid process and uncertain process. Journal of Uncertain Systems, 2, 3–16.
Liu, B. (2009a). Theory and practice of uncertain programming (2nd ed.). Berlin: Springer-Verlag.
Liu, B. (2009b). Some research problems in uncertainty theory. Journal of Uncertain Systems, 3, 3–10.
Liu, B. (2010a). Uncertainty theory: A branch of mathematics for modeling human uncertainty. Berlin: Springer-Verlag.
Liu, B. (2010b). Uncertain risk analysis and uncertain reliability analysis. Journal of Uncertain Systemsm, 4, 163–170.
Liu, B. (2012). Why is there a need for uncertainty theory? Journal of Uncertain Systems, 6, 3–10.
Liu B.,(2013) Toward uncertain finance theory, Journal of Uncertainty Analysis and Applications, 1, Article 1.
Liu, B. (2015). Uncertainty theory (4th ed.). Berlin: Springer-Verlag.
Murat, C., & Paschos, V. T. (2002). The probabilistic minimum vertex-covering problem. International Transactions in Operational Research, 9, 19–32.
Ni, Y., Xie, L., & Liu, Z. (2010). Minimizing the expected complete influence time of a social network. Information Sciences, 180, 2514–2527.
Ni, Y. (2012). Minimum weight covering problems in stochastic environments. Information Sciences, 214, 91–104.
Norman, R. Z., & Rabin, M. O. (1959). An algorithm for a minimum cover of a graph. Proceedings of the American Mathematical Society, 10, 315–319.
Oliveto, P. S., He, J., & Yao, X. (2009). Analysis of the (1+1)-EA for finding approximate solutions to vertex cover problems. IEEE Transactions on Evolutionary Computation, 13, 1006–1029.
Peng, Z., & Iwamura, K. (2010). A sufficient and necessary condition of uncertainty distribution. Journal of Interdisciplinary Mathematics, 13, 277–285.
Peng, J., Zhang, B., & Li, S. (2014). Towards uncertain network optimization, Journal of Uncertainty Analysis and Applications, to be published.
Shiue, W. T. (2005). Novel state minimization and state assignment in finite state machine design for low-power portable devices. Integration, the VLSI Journal, 38, 549–570.
Shyu, S. J., Yin, P. Y., & Lin, B. M. T. (2004). An ant colony optimization algorithm for the minimum weight vertex cover problem. Annals of Operations Research, 131, 283–304.
Sun, G., Liu, Y. K., & Lan, Y. (2011). Fuzzy two-stage material procurement planning problem. Journal of Intelligent Manufacturing, 22, 319–331.
Weigt, M., & Hartmann, A. K. (2000). Number of guards needed by a museum: A phase transition in vertex covering of random graphs. Physical Review Letters, 84, 6118–6121.
Yang, X., & Gao, J. (2013). Uncertain differential games with application to capitalism, Journal of Uncertainty Analysis and Applications, 1, Article 17.
Yao, K. (2013a). Extreme values and integral of solution of uncertain differential equation, Journal of Uncertainty Analysis and Applications, 1, Article 2.
Yao, K. (2013b). A type of nonlinear uncertain differential equations with analytic solution, Journal of Uncertainty Analysis and Applications, 1, Article 8.
Zhang, B., & Peng, J. (2012). Uncertain programming model for Chinese postman problem with uncertain weights. Industrial Engineering & Management Systems, 11, 18–25.
Zhu, Y. (2010). Uncertain optimal control with application to a portfolio selection model. Cybernetics and Systems, 41, 535–547.
Acknowledgments
This work is supported by the Projects of the Humanity and Social Science Foundation of Ministry of Education of China (No.13YJA630065), the Key Project of Hubei Provincial Natural Science Foundation (No.2012FFA065), the Scientific and Technological Innovation Team Project (No.T201110) of Hubei Provincial Department of Education, China, and the Fundamental Research Funds for the Central Universities (No. 31541411209).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Chen, L., Peng, J., Zhang, B. et al. Uncertain programming model for uncertain minimum weight vertex covering problem. J Intell Manuf 28, 625–632 (2017). https://doi.org/10.1007/s10845-014-1009-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10845-014-1009-1