Log in

Relevant bibliographies by topics / Minimum Vertex Cover Problem / Journal articles

Journal articles on the topic 'Minimum Vertex Cover Problem'

To see the other types of publications on this topic, follow the link: Minimum Vertex Cover Problem.

Author: Grafiati

Published: 10 December 2022

Last updated: 28 January 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Minimum Vertex Cover Problem.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Han, Keun-Hee, and Chan-Soo Kim. "Applying Genetic Algorithm to the Minimum Vertex Cover Problem." KIPS Transactions:PartB 15B, no. 6 (December 31, 2008): 609–12. http://dx.doi.org/10.3745/kipstb.2008.15-b.6.609.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

J., Kavitha. "DNA Computing towards the Solution of Minimum Vertex Cover Problem." International Journal of Psychosocial Rehabilitation 24, no. 5 (May 25, 2020): 6807–11. http://dx.doi.org/10.37200/ijpr/v24i5/pr2020672.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Hassin, Refael, and Asaf Levin. "The minimum generalized vertex cover problem." ACM Transactions on Algorithms 2, no. 1 (January 2006): 66–78. http://dx.doi.org/10.1145/1125994.1125998.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

SINGH, ALOK, and ASHOK KUMAR GUPTA. "A HYBRID HEURISTIC FOR THE MINIMUM WEIGHT VERTEX COVER PROBLEM." Asia-Pacific Journal of Operational Research 23, no. 02 (June 2006): 273–85. http://dx.doi.org/10.1142/s0217595906000905.

Full text

Abstract:

Given an undirected graph with weights associated with its vertices, the minimum weight vertex cover problem seeks a subset of vertices with minimum sum of weights such that each edge of the graph has at least one endpoint belonging to the subset. In this paper, we propose a hybrid approach, combining a steady-state genetic algorithm and a greedy heuristic, for the minimum weight vertex cover problem. The genetic algorithm generates vertex cover, which is then reduced to minimal weight vertex cover by the heuristic. We have evaluated the performance of our algorithm on several test problems of varying sizes. Computational results show the effectiveness of our approach in solving the minimum weight vertex cover problem.

APA, Harvard, Vancouver, ISO, and other styles

5

Tu, Jianhua. "A Survey on the k-Path Vertex Cover Problem." Axioms 11, no. 5 (April 20, 2022): 191. http://dx.doi.org/10.3390/axioms11050191.

Full text

Abstract:

Given an integer k ≥ 2, a k-path is a path on k vertices. A set of vertices in a graph G is called a k-path vertex cover if it includes at least one vertex of every k-path of G. A minimum k-path vertex cover in G is a k-path vertex cover having the smallest possible number of vertices and its cardinality is called the k-path vertex cover number of G. In the k-path vertex cover problem, the goal is to find a minimum k-path vertex cover in a given graph. In this paper, we present a brief survey of the current state of the art in the study of the k-path vertex cover problem and the k-path vertex cover number.

APA, Harvard, Vancouver, ISO, and other styles

6

Zhang, Yun Jia, Wei Wei, and Ting Wang. "Research of the Minimum Vertex-Cover Solutions on the Tree and Lattice Structures." Advanced Materials Research 989-994 (July 2014): 4926–29. http://dx.doi.org/10.4028/www.scientific.net/amr.989-994.4926.

Full text

Abstract:

We focus the solution space of a most fundamental problem - Minimum Vertex-Cover problem - in theoretical computer science. After some rigorous analysis, we provide the formation mechanism of minimum vertex-cover solutions on the tree and give the organization of these solutions on arbitrary lattice structure. By the results, we can easily calculate the solution numbers on these structures and have better understanding of the hardness of Minimum Vertex-Cover problem. The proposed study and algorithm can make a new way on detecting the essential difficulty of NP-complete problems and designing efficient algorithms on solving them.

APA, Harvard, Vancouver, ISO, and other styles

7

Wang, Rong Long, Zheng Tang, and Xin Shun Xu. "An Efficient Algorithm for Minimum Vertex Cover Problem." IEEJ Transactions on Electronics, Information and Systems 124, no. 7 (2004): 1494–99. http://dx.doi.org/10.1541/ieejeiss.124.1494.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Wang, Luzhi, Shuli Hu, Mingyang Li, and Junping Zhou. "An Exact Algorithm for Minimum Vertex Cover Problem." Mathematics 7, no. 7 (July 6, 2019): 603. http://dx.doi.org/10.3390/math7070603.

Full text

Abstract:

In this paper, we propose a branch-and-bound algorithm to solve exactly the minimum vertex cover (MVC) problem. Since a tight lower bound for MVC has a significant influence on the efficiency of a branch-and-bound algorithm, we define two novel lower bounds to help prune the search space. One is based on the degree of vertices, and the other is based on MaxSAT reasoning. The experiment confirms that our algorithm is faster than previous exact algorithms and can find better results than heuristic algorithms.

APA, Harvard, Vancouver, ISO, and other styles

9

Hasudungan, Rofilde, Dwi M. Pangestuty, Asslia J. Latifah, and Rudiman. "Solving Minimum Vertex Cover Problem Using DNA Computing." Journal of Physics: Conference Series 1361 (November 2019): 012038. http://dx.doi.org/10.1088/1742-6596/1361/1/012038.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Cai, Shaowei, Kaile Su, and Qingliang Chen. "EWLS: A New Local Search for Minimum Vertex Cover." Proceedings of the AAAI Conference on Artificial Intelligence 24, no. 1 (July 3, 2010): 45–50. http://dx.doi.org/10.1609/aaai.v24i1.7539.

Full text

Abstract:

A number of algorithms have been proposed for the Minimum Vertex Cover problem. However, they are far from satisfactory, especially on hard instances. In this paper, we introduce Edge Weighting Local Search (EWLS), a new local search algorithm for the Minimum Vertex Cover problem. EWLS is based on the idea of extending a partial vertex cover into a vertex cover. A key point of EWLS is to find a vertex set that provides a tight upper bound on the size of the minimum vertex cover. To this purpose, EWLS employs an iterated local search procedure, using an edge weighting scheme which updates edge weights when stuck in local optima. Moreover, some sophisticated search strategies have been taken to improve the quality of local optima. Experimental results on the broadly used DIMACS benchmark show that EWLS is competitive with the current best heuristic algorithms, and outperforms them on hard instances. Furthermore, on a suite of difficult benchmarks, EWLS delivers the best results and sets a new record on the largest instance.

APA, Harvard, Vancouver, ISO, and other styles

11

Wang, Yanfeng, Peipei Hu, Xuncai Zhang, and Guangzhao Cui. "DNA Self-Assembly for the Minimum Vertex Cover Problem." Advanced Science Letters 4, no. 1 (January 1, 2011): 74–79. http://dx.doi.org/10.1166/asl.2011.1178.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Karci, Ali, and Ahmet Arslan. "Bidirectional evolutionary heuristic for the minimum vertex-cover problem." Computers & Electrical Engineering 29, no. 1 (January 2003): 111–20. http://dx.doi.org/10.1016/s0045-7906(01)00018-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Chen, Jingrong, Lei Kou, and Xiaochuan Cui. "An Approximation Algorithm for the Minimum Vertex Cover Problem." Procedia Engineering 137 (2016): 180–85. http://dx.doi.org/10.1016/j.proeng.2016.01.248.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Chlebík, Miroslav, and Janka Chlebíková. "Crown reductions for the Minimum Weighted Vertex Cover problem." Discrete Applied Mathematics 156, no. 3 (February 2008): 292–312. http://dx.doi.org/10.1016/j.dam.2007.03.026.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Xu, Hong, T. K. Satish Kumar, and Sven Koenig. "A Linear-Time and Linear-Space Algorithm for the Minimum Vertex Cover Problem on Giant Graphs." Proceedings of the International Symposium on Combinatorial Search 8, no. 1 (September 1, 2021): 173–74. http://dx.doi.org/10.1609/socs.v8i1.18414.

Full text

Abstract:

In this paper, we develop the message passing based linear-time and linear-space MVC algorithm (MVC-MPL) for solving the minimum vertex cover (MVC) problem. MVC-MPL is based on heuristics derived from a theoretical analysis of message passing algorithms in the context of belief propagation. We show that MVC-MPL produces smaller vertex covers than other linear-time and linear-space algorithms.

APA, Harvard, Vancouver, ISO, and other styles

16

De Santis, Filomena, Luisa Gargano, Mikael Hammar, Alberto Negro, and Ugo Vaccaro. "Spider Covers and Their Applications." ISRN Discrete Mathematics 2012 (November 28, 2012): 1–11. http://dx.doi.org/10.5402/2012/347430.

Full text

Abstract:

We introduce two new combinatorial optimization problems: the Maximum Spider Problem and the Spider Cover Problem; we study their approximability and illustrate their applications. In these problems we are given a directed graph , a distinguished vertex , and a family D of subsets of vertices. A spider centered at vertex s is a collection of arc-disjoint paths all starting at s but ending into pairwise distinct vertices. We say that a spider covers a subset of vertices X if at least one of the endpoints of the paths constituting the spider other than s belongs to X. In the Maximum Spider Problem the goal is to find a spider centered at s that covers the maximum number of elements of the family D. Conversely, the Spider Cover Problem consists of finding the minimum number of spiders centered at s that covers all subsets in D. We motivate the study of the Maximum Spider and Spider Cover Problems by pointing out a variety of applications. We show that a natural greedy algorithm gives a 2-approximation algorithm for the Maximum Spider Problem and a -approximation algorithm for the Spider Cover Problem.

APA, Harvard, Vancouver, ISO, and other styles

17

Erves, Rija, and Aleksandra Tepeh. "3-path vertex cover and dissociation number of hexagonal graphs." Applicable Analysis and Discrete Mathematics, no. 00 (2022): 7. http://dx.doi.org/10.2298/aadm201009007e.

Full text

Abstract:

A subset P of vertices of a graph G is called a k-path vertex cover if every path of order k in G contains at least one vertex from P. The cardinality of a minimum k-path vertex cover is called the k-path vertex cover number of G, and is denoted by ?k(G). It is known that the problem of finding a minimum 3-path vertex cover is NP-hard for planar graphs. In this paper we establish an upper bound for ?3(G), where G is from an important family of planar graphs, called hexagonal graphs, arising from real world applications.

APA, Harvard, Vancouver, ISO, and other styles

18

Likas, Aristidis, and Andreas Stafylopatis. "A parallel algorithm for the minimum weighted vertex cover problem." Information Processing Letters 53, no. 4 (February 1995): 229–34. http://dx.doi.org/10.1016/0020-0190(94)00189-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Xu, XinShun, Zheng Tang, RongLong Wang, and XuGang Wang. "A new motion equation for the minimum vertex cover problem." Neurocomputing 56 (January 2004): 441–46. http://dx.doi.org/10.1016/j.neucom.2003.08.004.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Ma, Jingjing. "A Method for Solving the Minimum Vertex Covering Problem Based on Graphene." Journal of Nanoelectronics and Optoelectronics 16, no. 3 (March 1, 2021): 460–65. http://dx.doi.org/10.1166/jno.2021.2969.

Full text

Abstract:

Based on the characteristics of graphene, this paper designs a method to solve the Minimum Vertex Covering problem of a graph. We designed a DNA-graphene oxide reaction platform in advance. At the same time, we designed the single DNA strands corresponding to each edge, and used the single DNA strands of edges associated with each vertex to represent the vertex; then, the single DNA strands of edges representing the combination of vertices was added into the DNA-graphene oxide reaction platform, and the change of fluorescence signal was detected. According to the change of fluorescence signal, whether a combination of vertices is the vertex cover of a graph or not can be determined. Our method takes advantage of the excellent properties of graphene, which can reduce the complexity of solving the Minimum Vertex Covering problem of a graph. At the same time, the combination of DNA computing and Nanotechnology provides a new research idea for the future research of DNA computing.

APA, Harvard, Vancouver, ISO, and other styles

21

Kamde, Pravinkumar, and P. J. Kulkarni. "Minimum Vertex Cover Problem Optimization Using Hopfield Neural Network: Graph Theory Problem Optimization." International Journal of Technology, Knowledge, and Society 2, no. 4 (2006): 45–54. http://dx.doi.org/10.18848/1832-3669/cgp/v02i04/55553.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Pushpam, P. Roushini Leely, and Chitra Suseendran. "Secure vertex cover of a graph." Discrete Mathematics, Algorithms and Applications 09, no. 02 (April 2017): 1750026. http://dx.doi.org/10.1142/s1793830917500264.

Full text

Abstract:

We study the problem of using mobile guards to defend the vertices of a graph [Formula: see text] against a single attack on its vertices. A vertex cover of a graph [Formula: see text] is a set [Formula: see text] such that for each edge [Formula: see text], at least one of [Formula: see text] or [Formula: see text] is in [Formula: see text]. The minimum cardinality of a vertex cover is termed the vertex covering number and it is denoted by [Formula: see text]. In this context, we introduce a new protection strategy called the secure vertex cover[Formula: see text]SVC[Formula: see text] problem, where the guards are placed at the vertices of a graph, in order to protect the graph against a single attack on its vertices. We are concerned with the protection of [Formula: see text] against a single attack, using at most one guard per vertex and require the set of guarded vertices to be a vertex cover. In addition, if any guard moves along an edge to deal with an attack to an unguarded vertex, then the resulting placement of guards must also form a vertex cover. Formally, this protection strategy defends the vertices of a graph against a single attack and simultaneously protects the edges. We define a SVC to be a set [Formula: see text] such that [Formula: see text] is a vertex cover and for each [Formula: see text], there exists a [Formula: see text] such that [Formula: see text] is a vertex cover. The minimum cardinality of an SVC is called the secure vertex covering number and it is denoted by [Formula: see text]. In this paper, a few properties of SVC of a graph are studied and specific values of [Formula: see text] for few classes of well-known graphs are evaluated.

APA, Harvard, Vancouver, ISO, and other styles

23

DA SILVA, MARIANA O., GUSTAVO A. GIMENEZ-LUGO, and MURILO V. G. DA SILVA. "VERTEX COVER IN COMPLEX NETWORKS." International Journal of Modern Physics C 24, no. 11 (October 14, 2013): 1350078. http://dx.doi.org/10.1142/s0129183113500782.

Full text

Abstract:

A Minimum Vertex Cover is the smallest set of vertices whose removal completely disconnects a graph. In this paper, we perform experiments on a number of graphs from standard complex networks databases addressing the problem of finding a "good" vertex cover (finding an optimum is a NP-Hard problem). In particular, we take advantage of the ubiquitous power law distribution present on many complex networks. In our experiments, we show that running a greedy algorithm in a power law graph we can obtain a very small vertex cover typically about 1.02 times the theoretical optimum. This is an interesting practical result since theoretically we know that: (1) In a general graph, on n vertices a greedy approach cannot guarantee a factor better than ln n; (2) The best approximation algorithm known at the moment is very involved and has a much larger factor of [Formula: see text]. In fact, in the context of approximation within a constant factor, it is conjectured that there is no (2 – ϵ)-approximation algorithm for the problem; (3) Even restricted to power law graphs and probabilistic guarantees, the best known approximation rate is 1.5.

APA, Harvard, Vancouver, ISO, and other styles

24

Xu, Xinshun, Zheng Tang, Xiaoming Chen, and Jiahai Wang. "A Modified Hopfield Neural Network for the Minimum Vertex Cover Problem." IEEJ Transactions on Electronics, Information and Systems 124, no. 10 (2004): 2155–61. http://dx.doi.org/10.1541/ieejeiss.124.2155.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Chen, J. "Minimum-weight vertex cover problem for two-class resource connection graphs." Information Sciences 74, no. 1-2 (October 15, 1993): 53–71. http://dx.doi.org/10.1016/0020-0255(93)90127-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Xu, Xinshun, and Jun Ma. "An efficient simulated annealing algorithm for the minimum vertex cover problem." Neurocomputing 69, no. 7-9 (March 2006): 913–16. http://dx.doi.org/10.1016/j.neucom.2005.12.016.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Veremyev, Alexander, Alexey Sorokin, Vladimir Boginski, and Eduardo L. Pasiliao. "Minimum vertex cover problem for coupled interdependent networks with cascading failures." European Journal of Operational Research 232, no. 3 (February 2014): 499–511. http://dx.doi.org/10.1016/j.ejor.2013.08.008.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Li, Ruizhi, Shuli Hu, Shaowei Cai, Jian Gao, Yiyuan Wang, and Minghao Yin. "NuMWVC: A novel local search for minimum weighted vertex cover problem." Journal of the Operational Research Society 71, no. 9 (June 17, 2019): 1498–509. http://dx.doi.org/10.1080/01605682.2019.1621218.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Guo, Ping, Changsheng Quan, and Haizhu Chen. "MEAMVC: A Membrane Evolutionary Algorithm for Solving Minimum Vertex Cover Problem." IEEE Access 7 (2019): 60774–84. http://dx.doi.org/10.1109/access.2019.2915550.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Cai, S., K. Su, C. Luo, and A. Sattar. "NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover." Journal of Artificial Intelligence Research 46 (April 30, 2013): 687–716. http://dx.doi.org/10.1613/jair.3907.

Full text

Abstract:

The Minimum Vertex Cover (MVC) problem is a prominent NP-hard combinatorial optimization problem of great importance in both theory and application. Local search has proved successful for this problem. However, there are two main drawbacks in state-of-the-art MVC local search algorithms. First, they select a pair of vertices to exchange simultaneously, which is time-consuming. Secondly, although using edge weighting techniques to diversify the search, these algorithms lack mechanisms for decreasing the weights. To address these issues, we propose two new strategies: two-stage exchange and edge weighting with forgetting. The two-stage exchange strategy selects two vertices to exchange separately and performs the exchange in two stages. The strategy of edge weighting with forgetting not only increases weights of uncovered edges, but also decreases some weights for each edge periodically. These two strategies are used in designing a new MVC local search algorithm, which is referred to as NuMVC. We conduct extensive experimental studies on the standard benchmarks, namely DIMACS and BHOSLIB. The experiment comparing NuMVC with state-of-the-art heuristic algorithms show that NuMVC is at least competitive with the nearest competitor namely PLS on the DIMACS benchmark, and clearly dominates all competitors on the BHOSLIB benchmark. Also, experimental results indicate that NuMVC finds an optimal solution much faster than the current best exact algorithm for Maximum Clique on random instances as well as some structured ones. Moreover, we study the effectiveness of the two strategies and the run-time behaviour through experimental analysis.

APA, Harvard, Vancouver, ISO, and other styles

31

Cai, Shaowei, Kaile Su, and Abdul Sattar. "Two New Local Search Strategies for Minimum Vertex Cover." Proceedings of the AAAI Conference on Artificial Intelligence 26, no. 1 (September 20, 2021): 441–47. http://dx.doi.org/10.1609/aaai.v26i1.8125.

Full text

Abstract:

In this paper, we propose two new strategies to design efficient local search algorithms for the minimum vertex cover (MVC) problem. There are two main drawbacks in state-of-the-art MVC local search algorithms: First, they select a pair of vertices to be exchanged simultaneously, which is time consuming; Second, although they use edge weighting techniques, they do not have a strategy to decrease the weights. To address these drawbacks, we propose two new strategies: two stage exchange and edge weighting with forgetting. The two stage exchange strategy selects two vertices to be exchanged separately and performs the exchange in two stages. The strategy of edge weighting with forgetting not only increases weights of uncovered edges, but also decreases some weights for each edge periodically. We utilize these two strategies to design a new algorithm dubbed NuMVC. The experimental results show that NuMVC significantly outperforms existing state-of-the-art heuristic algorithms on most of the hard DIMACS instances and all instances in the hard random BHOSLIB benchmark.

APA, Harvard, Vancouver, ISO, and other styles

32

Balaji, S., S. T. Vikram, and G. Kanagasabapathy. "Jumping particle swarm optimisation method for solving minimum weight vertex cover problem." International Journal of Bio-Inspired Computation 18, no. 3 (2021): 143. http://dx.doi.org/10.1504/ijbic.2021.119198.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Kanagasabapathy, G., S. Balaji, and S. T. Vikram. "Jumping particle swarm optimisation method for solving minimum weight vertex cover problem." International Journal of Bio-Inspired Computation 18, no. 3 (2021): 143. http://dx.doi.org/10.1504/ijbic.2021.10043014.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Zhang, Y. J., X. D. Mu, X. W. Liu, X. Y. Wang, X. Zhang, K. Li, T. Y. Wu, D. Zhao, and C. Dong. "Applying the quantum approximate optimization algorithm to the minimum vertex cover problem." Applied Soft Computing 118 (March 2022): 108554. http://dx.doi.org/10.1016/j.asoc.2022.108554.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Cheng, Zhen, and Yufang Huang. "Implementation of Minimum Vertex Cover Problem Based on Tile Self-Assembly Model." Journal of Computational and Theoretical Nanoscience 10, no. 9 (September 1, 2013): 2123–30. http://dx.doi.org/10.1166/jctn.2013.3177.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Crescenzi, Pierluigi, and Luca Trevisan. "On the distributed decision-making complexity of the minimum vertex cover problem." RAIRO - Theoretical Informatics and Applications 30, no. 5 (1996): 431–41. http://dx.doi.org/10.1051/ita/1996300504311.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Li, Ruizhi, Shuli Hu, Haochen Zhang, and Minghao Yin. "An efficient local search framework for the minimum weighted vertex cover problem." Information Sciences 372 (December 2016): 428–45. http://dx.doi.org/10.1016/j.ins.2016.08.053.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Wu, Fan, Kenli Li, Ahmed Sallam, and Xu Zhou. "A molecular solution for minimum vertex cover problem in tile assembly model." Journal of Supercomputing 66, no. 1 (March 16, 2013): 148–69. http://dx.doi.org/10.1007/s11227-013-0892-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Chen, Jinkun, Yaojin Lin, Jinjin Li, Guoping Lin, Zhouming Ma, and Anhui Tan. "A rough set method for the minimum vertex cover problem of graphs." Applied Soft Computing 42 (May 2016): 360–67. http://dx.doi.org/10.1016/j.asoc.2016.02.003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Shyu, Shyong Jian, Peng-Yeng Yin, and Bertrand M. T. Lin. "An Ant Colony Optimization Algorithm for the Minimum Weight Vertex Cover Problem." Annals of Operations Research 131, no. 1-4 (October 2004): 283–304. http://dx.doi.org/10.1023/b:anor.0000039523.95673.33.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Zhou, Taoqing, Zhipeng Lü, Yang Wang, Junwen Ding, and Bo Peng. "Multi-start iterated tabu search for the minimum weight vertex cover problem." Journal of Combinatorial Optimization 32, no. 2 (May 29, 2015): 368–84. http://dx.doi.org/10.1007/s10878-015-9909-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Voß, Stefan, and Andreas Fink. "A hybridized tabu search approach for the minimum weight vertex cover problem." Journal of Heuristics 18, no. 6 (September 19, 2012): 869–76. http://dx.doi.org/10.1007/s10732-012-9211-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Pourhassan, Mojgan, Feng Shi, and Frank Neumann. "Parameterized Analysis of Multiobjective Evolutionary Algorithms and the Weighted Vertex Cover Problem." Evolutionary Computation 27, no. 4 (December 2019): 559–75. http://dx.doi.org/10.1162/evco_a_00255.

Full text

Abstract:

Evolutionary multiobjective optimization for the classical vertex cover problem has been analysed in Kratsch and Neumann ( 2013 ) in the context of parameterized complexity analysis. This article extends the analysis to the weighted vertex cover problem in which integer weights are assigned to the vertices and the goal is to find a vertex cover of minimum weight. Using an alternative mutation operator introduced in Kratsch and Neumann ( 2013 ), we provide a fixed parameter evolutionary algorithm with respect to [Formula: see text], the cost of an optimal solution for the problem. Moreover, we present a multiobjective evolutionary algorithm with standard mutation operator that keeps the population size in a polynomial order by means of a proper diversity mechanism, and therefore, manages to find a 2-approximation in expected polynomial time. We also introduce a population-based evolutionary algorithm which finds a [Formula: see text]-approximation in expected time [Formula: see text].

APA, Harvard, Vancouver, ISO, and other styles

44

Hu, Shuli, Xiaoli Wu, Huan Liu, Yiyuan Wang, Ruizhi Li, and Minghao Yin. "Multi-Objective Neighborhood Search Algorithm Based on Decomposition for Multi-Objective Minimum Weighted Vertex Cover Problem." Sustainability 11, no. 13 (July 2, 2019): 3634. http://dx.doi.org/10.3390/su11133634.

Full text

Abstract:

The multi-objective minimum weighted vertex cover problem aims to minimize the sum of different single type weights simultaneously. In this paper, we focus on the bi-objective minimum weighted vertex cover and propose a multi-objective algorithm integrating iterated neighborhood search with decomposition technique to solve this problem. Initially, we adopt the decomposition method to divide the multi-objective problem into several scalar optimization sub-problems. Meanwhile, to find more possible optimal solutions, we design a mixed score function according to the problem feature, which is applied in initializing procedure and neighborhood search. During the neighborhood search, three operators ( A d d , D e l e t e , S w a p ) explore the search space effectively. We performed numerical experiments on many instances, and the results show the effectiveness of our new algorithm (combining decomposition and neighborhood search with mixed score) on several experimental metrics. We compared our experimental results with the classical multi-objective algorithm non-dominated sorting genetic algorithm II. It was obviously shown that our algorithm can provide much better results than the comparative algorithm considering the different metrics.

APA, Harvard, Vancouver, ISO, and other styles

45

Pushpam, P. Roushini Leely, and Chitra Suseendran. "m-Secure vertex cover of a graph." Discrete Mathematics, Algorithms and Applications 10, no. 06 (December 2018): 1850075. http://dx.doi.org/10.1142/s1793830918500751.

Full text

Abstract:

In this paper, we use multiple guard movements to defend the edges of a graph [Formula: see text] against a single attack. At most, one guard is positioned at each vertex. To defend an attack on an edge, a guard at an incident vertex moves across the attacked edge and the other guards may move (or not) to the neighboring vertices to better configure themselves. This strategy requires the set of vertices containing guards to be a vertex cover before and after an attack. A suitable placement of guards is called an [Formula: see text]-secure vertex cover of [Formula: see text]. We call this the [Formula: see text]-secure vertex cover problem, where [Formula: see text] stands for the multiple guard movements. The minimum number of guards required to defend the edges of [Formula: see text] against a single attack using multiple guard movements is called the [Formula: see text]-secure vertex covering number and it is denoted by [Formula: see text]. In this paper we initiate a study of this parameter.

APA, Harvard, Vancouver, ISO, and other styles

46

Nagy, Benedek, and Péter Szokol. "A Genetic Algorithm for the Minimum Vertex Cover Problem with Interval-Valued Fitness." Acta Polytechnica Hungarica 18, no. 4 (2021): 105–23. http://dx.doi.org/10.12700/aph.18.4.2021.4.6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Wang, Yang, Zhipeng Lu, and Abraham P. Punnen. "A Fast and Robust Heuristic Algorithm for the Minimum Weight Vertex Cover Problem." IEEE Access 9 (2021): 31932–45. http://dx.doi.org/10.1109/access.2021.3051741.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Wang, Zhaocai, Dongmei Huang, and Renlin Pei. "Solving the Minimum Vertex Cover Problem with DNA Molecules in Adleman-Lipton Model." Journal of Computational and Theoretical Nanoscience 11, no. 2 (February 1, 2014): 521–23. http://dx.doi.org/10.1166/jctn.2014.3388.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Xie, Xiaojun, Xiaolin Qin, Chunqiang Yu, and Xingye Xu. "Test-cost-sensitive rough set based approach for minimum weight vertex cover problem." Applied Soft Computing 64 (March 2018): 423–35. http://dx.doi.org/10.1016/j.asoc.2017.12.023.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Gonzalez, Teofilo F. "A simple LP-free approximation algorithm for the minimum weight vertex cover problem." Information Processing Letters 54, no. 3 (May 1995): 129–31. http://dx.doi.org/10.1016/0020-0190(95)00022-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!