Добірка наукової літератури з теми "Minimum Vertex Cover Problem"
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся зі списками актуальних статей, книг, дисертацій, тез та інших наукових джерел на тему "Minimum Vertex Cover Problem".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Статті в журналах з теми "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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерела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.
Повний текст джерелаДисертації з теми "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.
Повний текст джерелаLevy, 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.
Повний текст джерелаFinally, 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.
Повний текст джерелаHIRATA, Tomio, and Hideaki OTSUKI. "Inapproximability of the Edge-Contraction Problem." Institute of Electronics, Information and Communication Engineers, 2006. http://hdl.handle.net/2237/15066.
Повний текст джерелаOuali, 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.
Повний текст джерелаChang, Ching-Chun, and 張景鈞. "On the Minimum Weighted Vertex Cover Problem." Thesis, 2017. http://ndltd.ncl.edu.tw/handle/66ufkr.
Повний текст джерела元智大學
資訊工程學系
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.
Повний текст джерела國立臺灣科技大學
工業管理系
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.
Повний текст джерела國立臺灣科技大學
工業管理系
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.
Повний текст джерела國立臺灣科技大學
資訊管理系
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.
Повний текст джерелаКниги з теми "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.
Знайти повний текст джерелаKonstantinou, 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.
Повний текст джерелаЧастини книг з теми "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.
Повний текст джерелаFang, 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.
Повний текст джерелаGao, 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.
Повний текст джерелаXu, 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.
Повний текст джерелаLi, 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.
Повний текст джерелаJovanovic, 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.
Повний текст джерелаThenepalle, 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.
Повний текст джерелаChen, 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.
Повний текст джерелаDekker, 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.
Повний текст джерелаTomá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.
Повний текст джерелаТези доповідей конференцій з теми "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.
Повний текст джерелаShimizu, 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.
Повний текст джерелаMousavian, 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.
Повний текст джерела"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.
Повний текст джерелаToume, 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.
Повний текст джерелаUgurlu, 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.
Повний текст джерелаTaoka, 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.
Повний текст джерелаZhang, 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.
Повний текст джерелаYeh, 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.
Повний текст джерелаZhang, 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.
Повний текст джерела