Relevant bibliographies by topics / Minimum Vertex Cover Problem

Academic literature on the topic '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:

Contents

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"

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
More sources

Dissertations / Theses on the topic "Minimum Vertex Cover Problem"

1

Imamura, Tomokazu. "Studies on approximation algorithms for the minimum vertex cover problem." 京都大学 (Kyoto University), 2007. http://hdl.handle.net/2433/135977.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

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.

Full text
Abstract:
We present a set of approximation results for several covering problems in dense graphs. These results show that for several problems, classical algorithms with constant approximation ratios can be analyzed in a finer way, and provide better constant approximation ratios under some density constraints. In particular, we show that the maximal matching heuristic approximates VERTEX COVER (VC) and MINIMUM MAXIMAL MATCHING (MMM) with a constant ratio strictly smaller than 2 when the proportion of edges present in the graph (weak density) is at least 3/4, or when the normalized minimum degree (strong density) is at least 1/2. We also show that this result can be improved by a greedy algorithm which provides a constant ratio smaller than 2 when the weak density is at least 1/2. We also provide tight families of graphs for all these approximation ratios. We then looked at several algorithms from the literature for VC and SET COVER (SC). We present a unified and critical approach to the Karpinski/Zelikovsky, Imamura/Iwama and Bar-Yehuda/Kehat algorithms, identifying the general the general scheme underlying these algorithms.

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

APA, Harvard, Vancouver, ISO, and other styles
3

Sinkovic, John Henry. "The Minimum Rank Problem for Outerplanar Graphs." BYU ScholarsArchive, 2013. https://scholarsarchive.byu.edu/etd/3722.

Full text
Abstract:
Given a simple graph G with vertex set V(G)={1,2,...,n} define S(G) to be the set of all real symmetric matrices A such that for all i not equal to j, the ijth entry of A is nonzero if and only if ij is in E(G). The range of the ranks of matrices in S(G) is of interest and can be determined by finding the minimum rank. The minimum rank of a graph, denoted mr(G), is the minimum rank achieved by a matrix in S(G). The maximum nullity of a graph, denoted M(G), is the maximum nullity achieved by a matrix in S(G). Note that mr(G)+M(G)=|V(G)| and so in finding the maximum nullity of a graph, the minimum rank of a graph is also determined. The minimum rank problem for a graph G asks us to determine mr(G) which in general is very difficult. A simple graph is planar if there exists a drawing of G in the plane such that any two line segments representing edges of G intersect only at a point which represents a vertex of G. A planar drawing partitions the rest of the plane into open regions called faces. A graph is outerplanar if there exists a planar drawing of G such that every vertex lies on the outer face. We consider the class of outerplanar graphs and summarize some of the recent results concerning the minimum rank problem for this class. The path cover number of a graph, denoted P(G), is the minimum number of vertex-disjoint paths needed to cover all the vertices of G. We show that for all outerplanar graphs G, P(G)is greater than or equal to M(G). We identify a subclass of outerplanar graphs, called partial 2-paths, for which P(G)=M(G). We give a different characterization for another subset of outerplanar graphs, unicyclic graphs, which determines whether M(G)=P(G) or M(G)=P(G)-1. We give an example of a 2-connected outerplanar graph for which P(G) ≥ M(G).A cover of a graph G is a collection of subgraphs of G such that the union of the edge sets of the subgraphs is equal to the E(G). The rank-sum of a cover C of G is denoted as rs(C) and is equal to the sum of the minimum ranks of the subgraphs in C. We show that for an outerplanar graph G, there exists an edge-disjoint cover of G consisting of cliques, stars, cycles, and double cycles such that the rank-sum of the cover is equal to the minimum rank of G. Using the fact that such a cover exists allows us to show that the minimum rank of a weighted outerplanar graph is equal to the minimum rank of its underlying simple graph.
APA, Harvard, Vancouver, ISO, and other styles
4

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Chang, Ching-Chun, and 張景鈞. "On the Minimum Weighted Vertex Cover Problem." Thesis, 2017. http://ndltd.ncl.edu.tw/handle/66ufkr.

Full text
Abstract:
碩士
元智大學
資訊工程學系
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.
APA, Harvard, Vancouver, ISO, and other styles
7

Halim, Christine, and 林貞平. "Minimum Cost Vertex-Disjoint Path Cover Problem." Thesis, 2016. http://ndltd.ncl.edu.tw/handle/h5f89x.

Full text
Abstract:
碩士
國立臺灣科技大學
工業管理系
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.
APA, Harvard, Vancouver, ISO, and other styles
8

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
Abstract:
碩士
國立臺灣科技大學
工業管理系
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.
APA, Harvard, Vancouver, ISO, and other styles
9

Liao, Guo-Jun, and 廖國鈞. "Weighted k-path Vertex Cover Problem in Cactus Graphs." Thesis, 2015. http://ndltd.ncl.edu.tw/handle/74897149092914985575.

Full text
Abstract:
碩士
國立臺灣科技大學
資訊管理系
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.
APA, Harvard, Vancouver, ISO, and other styles
10

Georgiou, Konstantinos. "Integrality Gaps for Strong Linear Programming and Semidefinite Programming Relaxations." Thesis, 2010. http://hdl.handle.net/1807/26271.

Full text
Abstract:
The inapproximability for NP-hard combinatorial optimization problems lies in the heart of theoretical computer science. A negative result can be either conditional, where the starting point is a complexity assumption, or unconditional, where the inapproximability holds for a restricted model of computation. Algorithms based on Linear Programming (LP) and Semidefinite Programming (SDP) relaxations are among the most prominent models of computation. The related and common measure of efficiency is the integrality gap, which sets the limitations of the associated algorithmic schemes. A number of systematic procedures, known as lift-and-project systems, have been proposed to improve the integrality gap of standard relaxations. These systems build strong hierarchies of either LP relaxations, such as the Lovasz-Schrijver (LS) and the Sherali-Adams (SA) systems, or SDP relaxations, such as the Lovasz-Schrijver SDP (LS+), the Sherali-Adams SDP (SA+) and the Lasserre (La) systems. In this thesis we prove integrality gap lower bounds for the aforementioned lift-and-project systems and for a number of combinatorial optimization problems, whose inapproximability is yet unresolved. Given that lift-and-project systems produce relaxations that have given the best algorithms known for a series of combinatorial problems, the lower bounds can be read as strong evidence of the inapproximability of the corresponding optimization problems. From the results found in the thesis we highlight the following: For every epsilon>0, the level-Omega(sqrt(log n/ log log n)) LS+ relaxation of the Vertex Cover polytope has integrality gap 2-epsilon. The integrality gap of the standard SDP for Vertex Cover remains 2-o(1) even if all hypermetric inequalities are added to the relaxation. The resulting relaxations are incomparable to the SDP relaxations derived by the LS+ system. Finally, the addition of all ell1 inequalities eliminates all solutions not in the integral hull. For every epsilon>0, the level-Omega(sqrt(log n/ log log n)) SA relaxation of Vertex Cover has integrality gap 2-epsilon. The integrality gap remains tight even for superconstant-level SA+ relaxations. We prove a tight lower bound for the number of tightenings that the SA system needs in order to prove the Pigeonhole Principle. We also prove sublinear and linear rank bounds for the La and SA systems respectively for the Tseitin tautology. Linear levels of the SA+ system treat highly unsatisfiable instances of fixed predicate-P constraint satisfaction problems over q-ary alphabets as fully satisfiable, when the satisfying assignments of the predicates P can be equipped with a balanced and pairwise independent distribution. We study the performance of the Lasserre system on the cut polytope. When the input is the complete graph on 2d+1 vertices, we show that the integrality gap is at least 1+1/(4d(d+1)) for the level-d SDP relaxation.
APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "Minimum Vertex Cover Problem"

1

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 text
APA, Harvard, Vancouver, ISO, and other styles
2

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.

Full text
Abstract:
The use of energy in buildings is a complex problem, but it can be reduced and alleviated by making appropriate decisions. Therefore, architects face a major and responsible task of designing the built environment in such a way that its energy dependence will be reduced to a minimum, while at the same time being able to provide comfortable living conditions. Today, architects have many tools at their disposal, facilitating the design process and simultaneously ensuring proper assessment in the early stages of building design. The purpose of this book is to present ongoing research from the universities involved in the project Creating the Network of Knowledge Labs for Sustainable and Resilient Environments (KLABS). This book attempts to highlight the problem of energy use in buildings and propose certain solutions. It consists of nine chapters, organised in three parts. The gathering of chapters into parts serves to identify the different themes that the designer needs to consider, namely energy resources, energy use and comfort, and energy efficiency. Part 1, entitled “Sustainable and Resilient Energy Resources,” sets off by informing the reader about the basic principles of energy sources, production, and use. The chapters give an overview of all forms of energies and energy cycle from resources to end users and evaluate the resilience of renewable energy systems. This information is essential to realise that the building, as an energy consumer, is part of a greater system and the decisions can be made at different levels. Part 2, entitled “Energy and Comfort in the Built Environment”, explain the relationship between energy use and thermal comfort in buildings and how it is predicted. Buildings consume energy to meet the users’ needs and to provide comfort. The appropriate selection of materials has a direct impact on the thermal properties of a building. Moreover, comfort is affected by parameters such as temperature, humidity, air movement, air quality, lighting, and noise. Understanding and calculating those conditions are valuable skills for the designers. After the basics of energy use in buildings have been explained, Part 3, entitled “Energy Saving Strategies” aims to provide information and tools that enable an energy- and environmentally-conscious design. This part is the most extensive as it aims to cover different design aspects. Firstly, passive and active measures that the building design needs to include are explained. Those measures are seen from the perspective of heat flow and generation. The Passive House concept, which is explained in the second chapter of Part 3, is a design approach that successfully incorporates such measures, resulting in low energy use by the building. Other considerations that the following chapters cover are solar control, embodied energy and CO2 emissions, and finally economic evaluation. The energy saving strategies explained in this book, despite not being exhaustive, provide basic knowledge that the designer can use and build upon during the design of new buildings and existing building upgrades. In the context of sustainability and resilience of the built environment, the reduction of energy demand is crucial. This book aims to provide a basic understanding of the energy flows in buildings and the subsequent impact for the building’s operation and its occupants. Most importantly, it covers the principles that need to be taken into account in energy efficient building design and demonstrates their effectiveness. Designers are shaping the built environment and it is their task to make energy-conscious and informed decisions that result in comfortable and resilient buildings.
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Minimum Vertex Cover Problem"

1

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 text
APA, Harvard, Vancouver, ISO, and other styles
2

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

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.

Full text
Abstract:
AbstractWe study efficient preprocessing for the undirected Feedback Vertex Set problem, a fundamental problem in graph theory which asks for a minimum-sized vertex set whose removal yields an acyclic graph. More precisely, we aim to determine for which parameterizations this problem admits a polynomial kernel. While a characterization is known for the related Vertex Cover problem based on the recently introduced notion of bridge-depth, it remained an open problem whether this could be generalized to Feedback Vertex Set. The answer turns out to be negative; the existence of polynomial kernels for structural parameterizations for Feedback Vertex Set is governed by the elimination distance to a forest. Under the standard assumption $$\textrm{NP}\not \subseteq \textrm{coNP}/\textrm{poly}$$, we prove that for any minor-closed graph class $$\mathcal {G}$$, Feedback Vertex Set parameterized by the size of a modulator to $$\mathcal {G}$$ has a polynomial kernel if and only if $$\mathcal {G}$$ has bounded elimination distance to a forest. This captures and generalizes all existing kernels for structural parameterizations of the Feedback Vertex Set problem.
APA, Harvard, Vancouver, ISO, and other styles
10

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Minimum Vertex Cover Problem"

1

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 text
APA, Harvard, Vancouver, ISO, and other styles
2

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

"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 text
APA, Harvard, Vancouver, ISO, and other styles
5

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Minimum Vertex Cover Problem' for particular source types:
Journal articles
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!

To the bibliography