Academic literature on the topic 'Minimum Vertex Cover Problem'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources 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.
Journal articles on the topic "Minimum Vertex Cover Problem"
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 textJ., 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 textHassin, 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 textSINGH, 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 textTu, 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 textZhang, 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 textWang, 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 textWang, 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 textHasudungan, 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 textCai, 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 textDissertations / Theses on the topic "Minimum Vertex Cover Problem"
Imamura, Tomokazu. "Studies on approximation algorithms for the minimum vertex cover problem." 京都大学 (Kyoto University), 2007. http://hdl.handle.net/2433/135977.
Full textLevy, Eythan. "Approximation algorithms for covering problems in dense graphs." Doctoral thesis, Universite Libre de Bruxelles, 2009. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210359.
Full textFinally, we look at the CONNECTED VERTEX COVER (CVC) problem,for which we proposed new approximation results in dense graphs. We first analyze Carla Savage's algorithm, then a new variant of the Karpinski-Zelikovsky algorithm. Our results show that these algorithms provide the same approximation ratios for CVC as the maximal matching heuristic and the Karpinski-Zelikovsky algorithm did for VC. We provide tight examples for the ratios guaranteed by both algorithms. We also introduce a new invariant, the "price of connectivity of VC", defined as the ratio between the optimal solutions of CVC and VC, and showed a nearly tight upper bound on its value as a function of the weak density. Our last chapter discusses software aspects, and presents the use of the GRAPHEDRON software in the framework of approximation algorithms, as well as our contributions to the development of this system.
/
Nous présentons un ensemble de résultats d'approximation pour plusieurs problèmes de couverture dans les graphes denses. Ces résultats montrent que pour plusieurs problèmes, des algorithmes classiques à facteur d'approximation constant peuvent être analysés de manière plus fine, et garantissent de meilleurs facteurs d'aproximation constants sous certaines contraintes de densité. Nous montrons en particulier que l'heuristique du matching maximal approxime les problèmes VERTEX COVER (VC) et MINIMUM MAXIMAL MATCHING (MMM) avec un facteur constant inférieur à 2 quand la proportion d'arêtes présentes dans le graphe (densité faible) est supérieure à 3/4 ou quand le degré minimum normalisé (densité forte) est supérieur à 1/2. Nous montrons également que ce résultat peut être amélioré par un algorithme de type GREEDY, qui fournit un facteur constant inférieur à 2 pour des densités faibles supérieures à 1/2. Nous donnons également des familles de graphes extrémaux pour nos facteurs d'approximation. Nous nous somme ensuite intéressés à plusieurs algorithmes de la littérature pour les problèmes VC et SET COVER (SC). Nous avons présenté une approche unifiée et critique des algorithmes de Karpinski-Zelikovsky, Imamura-Iwama, et Bar-Yehuda-Kehat, identifiant un schéma général dans lequel s'intègrent ces algorithmes.
Nous nous sommes finalement intéressés au problème CONNECTED VERTEX COVER (CVC), pour lequel nous avons proposé de nouveaux résultats d'approximation dans les graphes denses, au travers de l'algorithme de Carla Savage d'une part, et d'une nouvelle variante de l'algorithme de Karpinski-Zelikovsky d'autre part. Ces résultats montrent que nous pouvons obtenir pour CVC les mêmes facteurs d'approximation que ceux obtenus pour VC à l'aide de l'heuristique du matching maximal et de l'algorithme de Karpinski-Zelikovsky. Nous montrons également des familles de graphes extrémaux pour les ratios garantis par ces deux algorithmes. Nous avons également étudié un nouvel invariant, le coût de connectivité de VC, défini comme le rapport entre les solutions optimales de CVC et de VC, et montré une borne supérieure sur sa valeur en fonction de la densité faible. Notre dernier chapitre discute d'aspects logiciels, et présente l'utilisation du logiciel GRAPHEDRON dans le cadre des algorithmes d'approximation, ainsi que nos contributions au développement du logiciel.
Doctorat en Sciences
info:eu-repo/semantics/nonPublished
Sinkovic, John Henry. "The Minimum Rank Problem for Outerplanar Graphs." BYU ScholarsArchive, 2013. https://scholarsarchive.byu.edu/etd/3722.
Full textHIRATA, Tomio, and Hideaki OTSUKI. "Inapproximability of the Edge-Contraction Problem." Institute of Electronics, Information and Communication Engineers, 2006. http://hdl.handle.net/2237/15066.
Full textOuali, Mourad el [Verfasser]. "Randomized Approximation for the Matching and Vertex Cover Problem in Hypergraphs: Complexity and Algorithms / Mourad El Ouali." Kiel : Universitätsbibliothek Kiel, 2013. http://d-nb.info/1042185646/34.
Full textChang, Ching-Chun, and 張景鈞. "On the Minimum Weighted Vertex Cover Problem." Thesis, 2017. http://ndltd.ncl.edu.tw/handle/66ufkr.
Full text元智大學
資訊工程學系
105
For each B∈{0,1}, a B-skip vertex cover of an undirected graph G=(V,E) refers to a set of vertices which are incident to at least |E|-B edges. We show that given G, B and a weight function w:V→Z^+, a minimum B-skip vertex cover of weight at most ⌈log_2〖|V|〗 ⌉, if it exists, can be found in polynomial time. Our result and proof generalize those of Papadimitriou and Yannakakis.
Halim, Christine, and 林貞平. "Minimum Cost Vertex-Disjoint Path Cover Problem." Thesis, 2016. http://ndltd.ncl.edu.tw/handle/h5f89x.
Full text國立臺灣科技大學
工業管理系
104
This study presents a variant of the capacitated vehicle routing problem (CVRP), namely, the minimum cost vertex-disjoint path cover problem (MCVDPCP). In contrast to CVRP in which the vehicles start and end at the depot, vehicle routes in MCVDPCP involve a set of vertex-disjoint paths where a vehicle starts at a particular customer and finishes at another customer. Thus, MCVDPCP is defined to find a set of service paths to serve a set of customers with known geographical locations and demands; it aims to minimize the total of vehicle travel cost and vehicle activation cost. A hybrid approach that integrates variable neighborhood search (VNS) and tabu search (TS) is developed to solve the aforementioned problem. This algorithm presents the new concept of exploring a neighborhood solution by utilizing multi-neighborhood sets and applying the systematic changing neighborhood of VNS to modify a neighborhood set. TS is also incorporated into the algorithm to guide the search toward diverse regions. The proposed algorithm is tested on 14 instances of MCVDPCP, which are generated from well-known CVRP benchmark instances. Results indicate that the proposed algorithm efficiently solves MCVDPCP. Furthermore, a numerical experiment is performed on the problem using Taipei as the case study and considering the effects of vehicle capacity, maximum route duration, and demand variability.
Marpaung, Indri Claudia Magdalena, and 麥依林. "Particle Swarm Optimization for the Minimum Cost Vertex-Disjoint Path Cover Problem." Thesis, 2016. http://ndltd.ncl.edu.tw/handle/mzbyun.
Full text國立臺灣科技大學
工業管理系
104
In the minimum cost vertex–disjoint path cover problem (MCVDPCP), each vehicle serves customers directly from its location without having to start from or return to a depot. The aim of the MCVDPCP is to minimize the total vehicle travel cost without violating the vehicle capacity constraint and the maximum tour length. An application of the problem can be found in companies hiring freelance workers to serve customers to reduce operational costs. In this study, we propose a particle swarm optimization algorithm for solving the MCVDPCP with an aim at obtaining better results than the previous study.
Liao, Guo-Jun, and 廖國鈞. "Weighted k-path Vertex Cover Problem in Cactus Graphs." Thesis, 2015. http://ndltd.ncl.edu.tw/handle/74897149092914985575.
Full text國立臺灣科技大學
資訊管理系
103
A subset S of vertices in graph G is a k-path vertex cover if every path of order k in G contains at least one vertex from S. The cardinality of a minimum k-path vertex cover is called the k-path vertex cover number of a graph G. In this thesis, we consider the weighted version of a k-path vertex cover problem, in which vertices are given weights, and propose an O(n3) algorithm for solving this problem in cactus graphs.
Georgiou, Konstantinos. "Integrality Gaps for Strong Linear Programming and Semidefinite Programming Relaxations." Thesis, 2010. http://hdl.handle.net/1807/26271.
Full textBooks on the topic "Minimum Vertex Cover Problem"
Sreejit, Chakravarty, ed. Parallel and serial heuristics for the minimum set cover problem. Buffalo, N.Y: State University of New York at Buffalo, Dept. of Computer Science, 1990.
Find full textKonstantinou, Thaleia, Nataša Ćuković Ignjatović, and Martina Zbašnik-Senegačnik. ENERGY: resources and building performance. TU Delft Bouwkunde, 2018. http://dx.doi.org/10.47982/bookrxiv.25.
Full textBook chapters on the topic "Minimum Vertex Cover Problem"
Hassin, Refael, and Asaf Levin. "The Minimum Generalized Vertex Cover Problem." In Algorithms - ESA 2003, 289–300. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/978-3-540-39658-1_28.
Full textFang, Zhiwen, Yang Chu, Kan Qiao, Xu Feng, and Ke Xu. "Combining Edge Weight and Vertex Weight for Minimum Vertex Cover Problem." In Frontiers in Algorithmics, 71–81. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-08016-1_7.
Full textGao, Wanru, Tobias Friedrich, and Frank Neumann. "Fixed-Parameter Single Objective Search Heuristics for Minimum Vertex Cover." In Parallel Problem Solving from Nature – PPSN XIV, 740–50. Cham: Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-45823-6_69.
Full textXu, Hong, T. K. Satish Kumar, and Sven Koenig. "A New Solver for the Minimum Weighted Vertex Cover Problem." In Integration of AI and OR Techniques in Constraint Programming, 392–405. Cham: Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-33954-2_28.
Full textLi, Xiaosong, Zhao Zhang, and Xiaohui Huang. "Approximation Algorithm for the Minimum Connected $$k$$ -Path Vertex Cover Problem." In Combinatorial Optimization and Applications, 764–71. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-12691-3_56.
Full textJovanovic, Raka, and Stefan Voß. "Fixed Set Search Applied to the Minimum Weighted Vertex Cover Problem." In Lecture Notes in Computer Science, 490–504. Cham: Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-34029-2_31.
Full textThenepalle, Jayanth Kumar, and Purusotham Singamsetty. "An Articulation Point-Based Approximation Algorithm for Minimum Vertex Cover Problem." In Trends in Mathematics, 281–89. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-030-01120-8_32.
Full textChen, Xiaoming, Zheng Tang, Xinshun Xu, Songsong Li, Guangpu Xia, and Jiahai Wang. "An Algorithm Based on Hopfield Network Learning for Minimum Vertex Cover Problem." In Advances in Neural Networks – ISNN 2004, 430–35. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-28647-9_72.
Full textDekker, David, and Bart M. P. Jansen. "Kernelization for Feedback Vertex Set via Elimination Distance to a Forest." In Graph-Theoretic Concepts in Computer Science, 158–72. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-031-15914-5_12.
Full textTomás, Ana Paula, António Leslie Bajuelos, and Fábio Marques. "Approximation Algorithms to Minimum Vertex Cover Problems on Polygons and Terrains." In Lecture Notes in Computer Science, 869–78. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/3-540-44860-8_90.
Full textConference papers on the topic "Minimum Vertex Cover Problem"
Jingrong Chen and Ruihua Xu. "Minimum vertex cover problem based on ant colony algorithm." In 7th Advanced Forum on Transportation of China (AFTC 2011). IET, 2011. http://dx.doi.org/10.1049/cp.2011.1389.
Full textShimizu, Satoshi, Kazuaki Yamaguchi, Toshiki Saitoh, and Sumio Masuda. "A fast heuristic for the minimum weight vertex cover problem." In 2016 IEEE/ACIS 15th International Conference on Computer and Information Science (ICIS). IEEE, 2016. http://dx.doi.org/10.1109/icis.2016.7550782.
Full textMousavian, Aylin, Alireza Rezvanian, and Mohammad Reza Meybodi. "Cellular learning automata based algorithm for solving minimum vertex cover problem." In 2014 22nd Iranian Conference on Electrical Engineering (ICEE). IEEE, 2014. http://dx.doi.org/10.1109/iraniancee.2014.6999681.
Full text"A PRUNING BASED ANT COLONY ALGORITHM FOR MINIMUM VERTEX COVER PROBLEM." In International Conference on Evolutionary Computation. SciTePress - Science and and Technology Publications, 2009. http://dx.doi.org/10.5220/0002313802810286.
Full textToume, Kouta, Daiki Kinjo, and Morikazu Nakamura. "A GPU algorithm for minimum vertex cover problems." In INTERNATIONAL CONFERENCE OF COMPUTATIONAL METHODS IN SCIENCES AND ENGINEERING 2014 (ICCMSE 2014). AIP Publishing LLC, 2014. http://dx.doi.org/10.1063/1.4897834.
Full textUgurlu, Onur. "New heuristic algorithm for unweighted minimum vertex cover." In 2012 IV International Conference "Problems of Cybernetics and Informatics" (PCI). IEEE, 2012. http://dx.doi.org/10.1109/icpci.2012.6486444.
Full textTaoka, Satoshi, and Toshimasa Watanabe. "Performance comparison of approximation algorithms for the minimum weight vertex cover problem." In 2012 IEEE International Symposium on Circuits and Systems - ISCAS 2012. IEEE, 2012. http://dx.doi.org/10.1109/iscas.2012.6272111.
Full textZhang, Xuncai, Ying Niu, and Yanfeng Wang. "DNA Computing in Microreactors: A Solution to the Minimum Vertex Cover Problem." In 2011 Sixth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA). IEEE, 2011. http://dx.doi.org/10.1109/bic-ta.2011.34.
Full textYeh, Chung-Wei, and Kee-Rong Wu. "Molecular Solution to Minimum Vertex Cover Problem Using Surface-based DNA Computation." In 2009 International Conference on Information Management and Engineering (ICIME 2009). IEEE, 2009. http://dx.doi.org/10.1109/icime.2009.47.
Full textZhang, Xuncai, Wenjun Song, Ruili Fan, and Guangzhao Cui. "Three Dimensional DNA Self-Assembly Model for the Minimum Vertex Cover Problem." In 2011 4th International Symposium on Computational Intelligence and Design (ISCID). IEEE, 2011. http://dx.doi.org/10.1109/iscid.2011.94.
Full text