Open Access
| Issue |
RAIRO-Oper. Res.
Volume 59, Number 1, January-February 2025
|
|
|---|---|---|
| Page(s) | 397 - 408 | |
| DOI | https://doi.org/10.1051/ro/2024231 | |
| Published online | 13 February 2025 | |
- P. Alimonti and V. Kann, Some APX-completeness results for cubic graphs. Theor. Comput. Sci. 237 (2000) 123–134. [CrossRef] [Google Scholar]
- D. Angel, A graph theoretical approach for node covering in tree based architectures and its application to bioinformatics. Netw. Model. Anal. Health Inf. Bioinf. 8 (2019) 12. [CrossRef] [Google Scholar]
- D. Angel and A. Amutha, Exact covering of butterfly and Benes networks. Int. J. Pure Appl. Math. 101 (2015) 863–872. [Google Scholar]
- D. Angel and A. Amutha, On covering the nodes of circulant networks and its applications. Wireless Pers. Commun. 94 (2017) 2163–2172. [CrossRef] [Google Scholar]
- D. Avis and T. Imamura, A list heuristic for vertex cover. Oper. Res. Lett. 35 (2007) 201–204. [CrossRef] [MathSciNet] [Google Scholar]
- R. Bar-Yehuda and S. Even, A Local-Ratio theorem for approximating the weighted vertex cover problem. North-Holland Math. Stud. 109 (1985) 27–45. [Google Scholar]
- B. Behsaz, P. Hatami and E.S. Mahmoodian, On minimum vertex cover of generalized Petersen graphs. Aus. J. Comb. 40 (2007) 253–264. [Google Scholar]
- S. Cai, K. Su and Q. Chen, EWLS: a new local search for minimum vertex cover, in Twenty-Fourth AAAI Conference on Artificial Intelligence (2010) 45–50. [Google Scholar]
- J. Chen, I.A. Kanj and G. Xia, Improved upper bounds for vertex cover. Theor. Comput. Sci. 411 (2010) 3736–3756. [CrossRef] [Google Scholar]
- J. Chen, L. Kou and X. Cui, An approximation algorithm for the minimum vertex cover problem. Proc. Eng. 137 (2016) 180–185. [CrossRef] [Google Scholar]
- J. Cheetham, F. Dehne, A. Rau-Chaplin, U. Stege and P. Taillon, Solving large FPT problems on coarse-grained parallel machines. J. Comput. Syst. Sci. 67 (2003) 691–706. [CrossRef] [Google Scholar]
- Z.A. Dagdeviren, A metaheuristic algorithm for vertex cover based link monitoring and backbone formation in wireless ad hoc networks. Expert Syst. App. 213 (2023) 118–919. [Google Scholar]
- E. DeLaViña, W. Goddard, M.A. Henning, R. Pepper and E.R. Vaughan, Bounds on the k-domination number of a graph, Appl. Math. Lett. 24 (2011) 996–998. [CrossRef] [MathSciNet] [Google Scholar]
- F.F. Dragan and A. Brandstadt, A r-dominating cliques in graphs with hypertree structure. Discrete Math. 162 (1996) 93–108. [CrossRef] [MathSciNet] [Google Scholar]
- E. Filiol, E. Franc, A. Gubbioli, B. Moquet and G. Roblot, Combinatorial optimisation of worm propagation on an unknown network. Int. J. Comput. Electr. Autom. Control Inf. Eng. 1 (2007) 2931–2937. [Google Scholar]
- T. Gallai, Über extreme Punkt- und Kantenmengen. Ann. Univ. Sci. Budapest Eötvös Sec. Math. 2 (1959) 133–138. [Google Scholar]
- W. Hong and Z. Wang, Improved approximation algorithm for the combination of parallel machine scheduling and vertex cover. Int. J. Found. Comput. Sci. 28 (2017) 977–992. [CrossRef] [Google Scholar]
- G. Karakostas, A better approximation ratio for the vertex cover problem. Electron. Colloq. Comput. Complexity 5 (2009) 1–8. [Google Scholar]
- R.M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations. Springer, Boston, MA (1972) 85–103. [CrossRef] [Google Scholar]
- Z.J. Li and J.B. Wang, An analytical study of quantum walk through glued-tree graphs. J. Phys. A Math. Theor. 48 (2015) 1–20. [Google Scholar]
- A. Lingas, M. Miotk, J. Topp and P. ˙Zyliński, Graphs with equal domination and covering numbers. J. Comb. Optim. 39 (2020) 55–71. [CrossRef] [MathSciNet] [Google Scholar]
- C. Savage, Depth-first search and the vertex cover problem. Inf. Proccess. Lett. 14 (1982) 233–235. [CrossRef] [Google Scholar]
- F. Shaveisi, Lower bounds on the vertex cover number and energy of graphs. MATCH Commun. Math. Comput. Chem. 87 (2022) 683–692. [CrossRef] [MathSciNet] [Google Scholar]
- Z. Wang, D. Huang and R. Pei, Solving the minimum vertex cover problem with DNA molecules in Adleman–Lipton model. J. Comput. Theor. Nanosci. 11 (2014) 521–523. [CrossRef] [Google Scholar]
- D.B. West, Introduction to Graph Theory, 2nd edition. Prentice Hall (2001). [Google Scholar]
- X. Yang, G.M. Megson, Y. Tang and D.J. Evans, Diameter of parallelogramic honeycomb torus. Comput. Math. App. 50 (2005) 1477–1486. [Google Scholar]
- Y. Yigit, V.K. Akram and O. Dagdeviren, Breadth-first search tree integrated vertex cover algorithms for link monitoring and routing in wireless sensor networks. Comput. Netw. 194 (2021) 108–144. [Google Scholar]
- Y. Zhang, S. Wang, C. Liu and E. Zhu, TIVC: an efficient local search algorithm for minimum vertex cover in large graphs. Sensors 23 (2023) 7831. [CrossRef] [PubMed] [Google Scholar]
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.