A novel algorithm for the vertex cover problem based on minimal elements of discernibility matrix | International Journal of Machine Learning and Cybernetics Skip to main content
Springer Nature Link
Log in

A novel algorithm for the vertex cover problem based on minimal elements of discernibility matrix

  • Original Article
  • Published:
International Journal of Machine Learning and Cybernetics Aims and scope Submit manuscript

Abstract

Minimal vertex cover problem (MVCP) is a famous important NP-hard problem in graph theory. It has been reported that MVCP is equivalent to finding reducts of information systems in rough sets theory. This relationship motivates our idea to deal with MVCP in terms of approaches to discernibility matrix in rough set. First we point out that only minimal elements in the discernibility matrix are useful for MVCP, and we present a novel algorithm based on minimal elements for MVCP. Then we make experimental comparisons to demonstrate the effectiveness of this new algorithm on big graphs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Bondy JA, Murty USR (2008) Graph theory. In: Graduate texts in mathematics, vol 244. Springer, London

    Book  Google Scholar 

  2. Bondy JA, Murty USR (1976) Graph theory with applications, vol 290. Macmillan, London

    Book  Google Scholar 

  3. Sáenz-de Cabezón E, Wynn HP (2014) Measuring the robustness of a network using minimal vertex covers. Math Comput Simulation 104:82–94

    Article  MathSciNet  Google Scholar 

  4. Chen D, Yang YY (2014) Attribute reduction for heterogeneous data based on the combination of classical and fuzzy rough set models. IEEE Trans Fuzzy Syst 22(5):1325–1334

    Article  MathSciNet  Google Scholar 

  5. Chen D, Zhao S, Zhang L, Yang Y, Zhang X (2012) Sample pair selection for attribute reduction with rough set. IEEE Trans Knowl Data Eng 11:2080–2093

    Article  Google Scholar 

  6. Chen J, Li J (2012) An application of rough sets to graph theory. Inf Sci 201:114–127

    Article  MathSciNet  Google Scholar 

  7. Chen J, Lin Y, Li J, Lin G, Ma Z, Tan A (2016) A rough set method for the minimum vertex cover problem of graphs. Appl Soft Comput 42:360–367

    Article  Google Scholar 

  8. Chen J, Lin Y, Lin G, Li J, Ma Z (2015) The relationship between attribute reducts in rough sets and minimal vertex covers of graphs. Inf Sci 325:87–97

    Article  MathSciNet  Google Scholar 

  9. Chvatal V (1979) A greedy heuristic for the set-covering problem. Math Oper Res 4(3):233–235

    Article  MathSciNet  Google Scholar 

  10. Degang C, Changzhong W, Qinghua H (2007) A new approach to attribute reduction of consistent and inconsistent covering decision systems with covering rough sets. Inf Sci 177(17):3500–3518

    Article  MathSciNet  Google Scholar 

  11. Eiter T, Gottlob G (1995) Identifying the minimal transversals of a hypergraph and related problems. SIAM J Comput 24(6):1278–1304

    Article  MathSciNet  Google Scholar 

  12. Gomes FC, Meneses CN, Pardalos PM, Viana GVR (2006) Experimental analysis of approximation algorithms for the vertex cover and set covering problems. Comput Oper Res 33(12):3520–3534

    Article  Google Scholar 

  13. Hochbaum DS (1982) Approximation algorithms for the set covering and vertex cover problems. SIAM J Comput 11(3):555–556

    Article  MathSciNet  Google Scholar 

  14. Hu Q, Yu D, Liu J, Wu C (2008) Neighborhood rough set based heterogeneous feature subset selection. Inf Sci 178(18):3577–3594

    Article  MathSciNet  Google Scholar 

  15. Karaoğlan İ, Erdoğan G, Koç Ç (2018) The multi-vehicle probabilistic covering tour problem. Eur J Oper Res 271(1):278–287

    Article  MathSciNet  Google Scholar 

  16. Li J, Kumar CA, Mei C, Wang X (2017) Comparison of reduction in formal decision contexts. Int J Approx Reason 80:100–122

    Article  MathSciNet  Google Scholar 

  17. Li J, Mei C, Lv Y (2013) Incomplete decision contexts: approximate concept construction, rule acquisition and knowledge reduction. Int J Approx Reason 54(1):149–165

    Article  MathSciNet  Google Scholar 

  18. Listrovoy S, Minukhin S (2012) The solution algorithms for problems on the minimal vertex cover in networks and the minimal cover in boolean matrixes. Int J Comput Sci Issues (IJCSI) 9(5):8

    Google Scholar 

  19. Miao Z, Ye D, Zhang CQ (2013) Circuit extension and circuit double cover of graphs. Discret Math 313(20):2055–2060

    Article  MathSciNet  Google Scholar 

  20. Pawlak Z (1982) Rough sets. Int J Comput Inf Sci 11(5):341–356

    Article  Google Scholar 

  21. Pawlak Z (1991) Rough sets: theoretical aspects of reasoning about data. Theory and decision Library D: system theory, knowledge engineering and problem solving, vol 9. Springer, Netherlands

    Book  Google Scholar 

  22. Potočnik P, Šajna M, Verret G (2007) Mobility of vertex-transitive graphs. Discret Math 307(3–5):579–591

    Article  MathSciNet  Google Scholar 

  23. Qingyuan X, Anhui T, Jinjin L (2016) A rough set method for the vertex cover problem in graph theory. J Intell Fuzzy Syst 30(4):2003–2013

    Article  Google Scholar 

  24. Shu W, Qian W (2014) A fast approach to attribute reduction from perspective of attribute measures in incomplete decision systems. Knowl Based Syst 72:60–71

    Article  Google Scholar 

  25. Skowron A, Rauszer C (1992) The discernibility matrices and functions in information systems. Intelligent decision support. Springer, New York, pp 331–362

    Chapter  Google Scholar 

  26. Wang C, He Q, Chen D, Hu Q (2014) A novel method for attribute reduction of covering decision systems. Inf Sci 254:181–196

    Article  MathSciNet  Google Scholar 

  27. Wang Z, Cui Z (2012) Combination of parallel machine scheduling and vertex cover. Theor Comput Sci 460:10–15

    Article  MathSciNet  Google Scholar 

  28. Xie X, Qin X, Yu C, Xu X (2018) Test-cost-sensitive rough set based approach for minimum weight vertex cover problem. Appl Soft Comput 64:423–435

    Article  Google Scholar 

  29. Xu Q, Tan A, Lin Y (2017) A rough set method for the unicost set covering problem. Int J Mach Learn Cybern 8(3):781–792

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mathematics and Physics, North China Electric Power University, Beijing, 102206, People’s Republic of China

    Shengyang Zhuang & Degang Chen

Authors
  1. Shengyang Zhuang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Degang Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Shengyang Zhuang.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhuang, S., Chen, D. A novel algorithm for the vertex cover problem based on minimal elements of discernibility matrix. Int. J. Mach. Learn. & Cyber. 10, 3467–3474 (2019). https://doi.org/10.1007/s13042-019-00933-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13042-019-00933-6

Keywords

Search

Navigation