文章基本信息

标题：The solution algorithms for problems on the minimal vertex cover in networks and the minimal cover in Boolean matrixes
本地全文：下载
作者：Sergey Listrovoy ; Sergii Minukhin
期刊名称：International Journal of Computer Science Issues
印刷版ISSN：1694-0784
电子版ISSN：1694-0814
出版年度：2012
卷号：9
期号：5
出版社：IJCSI Press
摘要：The authors propose approximate algorithms for solving the problem of the minimal vertex cover of arbitrary graphs and the problem of minimal cover on the basis of their reduction, respectively, to the problems of quadratic and nonlinear Boolean programming, their specificity allowing to construct algorithms with time complexity not exceeding O (mn2), where in the case of solving the problem of minimal vertex cover of arbitrary graphs n is the number of vertices in the graph, m is the number of edges in the graph, and in the case of solving the problem of minimal cover n is the number of columns in the Boolean matrix, m is the number of rows in Boolean matrix.
关键词：vertex covers in graph; the minimal cover; Boolean matrix; time complexity