Log in

Relevant bibliographies by topics / Connected vertex cover problem

Contents

Journal articles
Dissertations / Theses
Books
Book chapters
Conference papers

Academic literature on the topic 'Connected vertex cover problem'

Author: Grafiati

Published: 4 June 2021

Last updated: 11 February 2022

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

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Connected 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 "Connected vertex cover problem"

1

Zhang, Yongfei, Jun Wu, Liming Zhang, Peng Zhao, Junping Zhou, and Minghao Yin. "An Efficient Heuristic Algorithm for Solving Connected Vertex Cover Problem." Mathematical Problems in Engineering 2018 (September 6, 2018): 1–10. http://dx.doi.org/10.1155/2018/3935804.

Full text

Abstract:

The connected vertex cover (CVC) problem, which has many important applications, is a variant of the vertex cover problem, such as wireless network design, routing, and wavelength assignment problem. A good algorithm for the problem can help us improve engineering efficiency, cost savings, and resources consumption in industrial applications. In this work, we present an efficient algorithm GRASP-CVC (Greedy Randomized Adaptive Search Procedure for Connected Vertex Cover) for CVC in general graphs. The algorithm has two main phases, i.e., construction phase and local search phase. In the constr

APA, Harvard, Vancouver, ISO, and other styles

2

Li, Yuchao, Wei Wang, and Zishen Yang. "The connected vertex cover problem in k-regular graphs." Journal of Combinatorial Optimization 38, no. 2 (2019): 635–45. http://dx.doi.org/10.1007/s10878-019-00403-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Li, Yuchao, Zishen Yang, and Wei Wang. "Complexity and algorithms for the connected vertex cover problem in 4-regular graphs." Applied Mathematics and Computation 301 (May 2017): 107–14. http://dx.doi.org/10.1016/j.amc.2016.12.004.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Liu, Xianliang, Hongliang Lu, Wei Wang, and Weili Wu. "PTAS for the minimum k-path connected vertex cover problem in unit disk graphs." Journal of Global Optimization 56, no. 2 (2011): 449–58. http://dx.doi.org/10.1007/s10898-011-9831-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Escoffier, Bruno, Laurent Gourvès, and Jérôme Monnot. "Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs." Journal of Discrete Algorithms 8, no. 1 (2010): 36–49. http://dx.doi.org/10.1016/j.jda.2009.01.005.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Rana, Akul, Anita Pal, and Madhumangal Pal. "An Efficient Algorithm to Solve the Conditional Covering Problem on Trapezoid Graphs." ISRN Discrete Mathematics 2011 (November 17, 2011): 1–10. http://dx.doi.org/10.5402/2011/213084.

Full text

Abstract:

Let G=(V,E) be a simple connected undirected graph. Each vertex v∈V has a cost c(v) and provides a positive coverage radius R(v). A distance duv is associated with each edge {u,v}∈E, and d(u,v) is the shortest distance between every pair of vertices u,v∈V. A vertex v can cover all vertices that lie within the distance R(v), except the vertex itself. The conditional covering problem is to minimize the sum of the costs required to cover all the vertices in G. This problem is NP-complete for general graphs, even it remains NP-complete for chordal graphs. In this paper, an O(n2) time algorithm to

APA, Harvard, Vancouver, ISO, and other styles

7

Wang, Limin, Xiaoyan Zhang, Zhao Zhang, and Hajo Broersma. "A PTAS for the minimum weight connected vertex cover P3 problem on unit disk graphs." Theoretical Computer Science 571 (March 2015): 58–66. http://dx.doi.org/10.1016/j.tcs.2015.01.005.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Fan, Lidan, Zhao Zhang, and Wei Wang. "PTAS for minimum weighted connected vertex cover problem with c-local condition in unit disk graphs." Journal of Combinatorial Optimization 22, no. 4 (2010): 663–73. http://dx.doi.org/10.1007/s10878-010-9315-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

DINITZ, YEFIM, MATTHEW J. KATZ, and ROI KRAKOVSKI. "GUARDING RECTANGULAR PARTITIONS." International Journal of Computational Geometry & Applications 19, no. 06 (2009): 579–94. http://dx.doi.org/10.1142/s0218195909003131.

Full text

Abstract:

A rectangular partition is a partition of a rectangle into non-overlapping rectangles, such that no four rectangles meet at a common point. A vertex guard is a guard located at a vertex of the partition (i.e., at a corner of a rectangle); it guards the rectangles that meet at this vertex. An edge guard is a guard that patrols along an edge of the partition, and is thus equivalent to two adjacent vertex guards. We consider the problem of finding a minimum-cardinality guarding set for the rectangles of the partition. For vertex guards, we prove that guarding a given subset of the rectangles is N

APA, Harvard, Vancouver, ISO, and other styles

10

Wang, Limin, Wenxue Du, Zhao Zhang, and Xiaoyan Zhang. "A PTAS for minimum weighted connected vertex cover $$P_3$$ P 3 problem in 3-dimensional wireless sensor networks." Journal of Combinatorial Optimization 33, no. 1 (2015): 106–22. http://dx.doi.org/10.1007/s10878-015-9937-z.

Full text

APA, Harvard, Vancouver, ISO, and other styles

More sources

Dissertations / Theses on the topic "Connected vertex cover problem"

1

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

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 (stro

APA, Harvard, Vancouver, ISO, and other styles

3

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

4

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

5

Cameron, Amy. "Approximation Algorithms for Network Connectivity Problems." Thèse, Université d'Ottawa / University of Ottawa, 2012. http://hdl.handle.net/10393/22734.

Full text

Abstract:

In this dissertation, we examine specific network connectivity problems, and achieve improved approximation algorithm and integrality gap results for them. We introduce an important new, highly useful and applicable, network connectivity problem - the Vital Core Connectivity Problem (VCC). Despite its many practical uses, this problem has not been previously studied. We present the first constant factor approximation algorithm for VCC, and provide an upper bound on the integrality gap of its linear programming relaxation. We also introduce a new, useful, extension of the minimum spanning tr

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:

碩士<br>元智大學<br>資訊工程學系<br>105<br>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:

碩士<br>國立臺灣科技大學<br>工業管理系<br>104<br>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 a

APA, Harvard, Vancouver, ISO, and other styles

8

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:

碩士<br>國立臺灣科技大學<br>資訊管理系<br>103<br>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

9

Dorai, Mahesh. "A reconfigurable computing solution to the parameterized vertex cover problem." 2004. http://etd.utk.edu/2004/DoraiMahesh.pdf.

Full text

Abstract:

Thesis (M.S.)--University of Tennessee, Knoxville, 2004.<br>Title from title page screen (viewed May 21, 2004). Thesis advisor: Gregory D. Peterson. Document formatted into pages (x, 117 p. : ill. (some col.)). Vita. Includes bibliographical references (p. 66-72).

APA, Harvard, Vancouver, ISO, and other styles

10

Tu, Hai-Lun, and 杜海倫. "The Approximability of Capacitated Vertex Cover Problem with Relaxed Constraints." Thesis, 2019. http://ndltd.ncl.edu.tw/handle/jkt8fr.

Full text

Abstract:

博士<br>國立臺灣大學<br>資訊工程學研究所<br>107<br>In this dissertation, we aim to address the approximability of the capacitated vertex cover (CVC) problem, i.e., a generic demand-to-service assignment model of the classical vertex cover problem, when certain constraints of interest are relaxed. In CVC, we are given a hypergraph H = (V, E) with a maximum edge size f. Each (hyper)edge is associated with a demand and each vertex is associated with a weight (cost), a capacity, and an available multiplicity. The objective is to find a minimum-weight vertex multiset, or cover, such that the demands of the edges c

APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "Connected vertex cover problem"

1

Borges, Rodrigo, Claudio de Almeida, and Peter D. Klein, eds. Explaining Knowledge. Oxford University Press, 2017. http://dx.doi.org/10.1093/oso/9780198724551.001.0001.

Full text

Abstract:

This is an edited collection of twenty-three new papers on the Gettier Problem and the issues connected with it. The set of authors includes many of the major figures in contemporary epistemology who have developed some of the well-known responses to the problem, and it also contains some younger epistemologists who bring new perspectives to the issues raised in the literature. Together, they cover the state of the art on virtually every epistemological and methodological aspect of the Gettier Problem. The volume also includes some skeptical voices according to which the Gettier Problem is not

APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Connected vertex cover problem"

1

Fujito, Toshihiro, and Tomoya Nakamura. "Eternal Connected Vertex Cover Problem." In Lecture Notes in Computer Science. Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-59267-7_16.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Khosravian Ghadikoalei, Mehdi, Nikolaos Melissinos, Jérôme Monnot, and Aris Pagourtzis. "Extension and Its Price for the Connected Vertex Cover Problem." In Lecture Notes in Computer Science. Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-25005-8_26.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Li, Xiaosong, Zhao Zhang, and Xiaohui Huang. "Approximation Algorithm for the Minimum Connected $$k$$ -Path Vertex Cover Problem." In Combinatorial Optimization and Applications. 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

4

Delbot, François, Christian Laforest, and Stephane Rovedakis. "Self-stabilizing Algorithms for Connected Vertex Cover and Clique Decomposition Problems." In Lecture Notes in Computer Science. Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-14472-6_21.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Cygan, Marek. "Deterministic Parameterized Connected Vertex Cover." In Algorithm Theory – SWAT 2012. Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-31155-0_9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Fujito, Toshihiro. "On Approximability of Connected Path Vertex Cover." In Approximation and Online Algorithms. Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-89441-6_2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Kumar, Mehul, Amit Kumar, and C. Pandu Rangan. "Reoptimization of Path Vertex Cover Problem." In Lecture Notes in Computer Science. Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-26176-4_30.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Shah, Kartik, Praveenkumar Reddy, and R. Selvakumar. "Vertex Cover Problem—Revised Approximation Algorithm." In Advances in Intelligent Systems and Computing. Springer India, 2014. http://dx.doi.org/10.1007/978-81-322-2126-5_2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Hassin, Refael, and Asaf Levin. "The Minimum Generalized Vertex Cover Problem." In Algorithms - ESA 2003. 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

10

Dai, Wenqiang. "Some Results on Incremental Vertex Cover Problem." In Algorithmic Aspects in Information and Management. Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-14355-7_12.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Connected vertex cover problem"

1

Arcencio, Guilherme G., Matheus T. Mattioli, Pedro H. D. B. Hokama, and Mário César San Felice. "Spanning Cover Inequalities for the Capacitated Vehicle Routing Problem." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2021. http://dx.doi.org/10.5753/etc.2021.16387.

Full text

Abstract:

In the k-Minimum Spanning Subgraph problem with d-Degree Center we want to find a minimum cost spanning connected subgraph with n - 1 + k edges and at least degree d in the center vertex, with n being the number of vertices. In this paper we describe an algorithm for this problem and present correctness demonstrations which we believe are simpler than those found in the literature. A solution for the k-Minimum Spanning Subgraph problem with d-Degree can be used to formulate spanning cover inequalities for the capacitated vehicle routing problem.

APA, Harvard, Vancouver, ISO, and other styles

2

Oliveto, P. S., J. He, and X. Yao. "Evolutionary algorithms and the Vertex Cover problem." In 2007 IEEE Congress on Evolutionary Computation. IEEE, 2007. http://dx.doi.org/10.1109/cec.2007.4424701.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Dahiya, Sonika. "A New Approximation Algorithm for Vertex Cover Problem." In 2013 International Conference on Machine Intelligence and Research Advancement (ICMIRA). IEEE, 2013. http://dx.doi.org/10.1109/icmira.2013.100.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Kratsch, Stefan, and Frank Neumann. "Fixed-parameter evolutionary algorithms and the vertex cover problem." In the 11th Annual conference. ACM Press, 2009. http://dx.doi.org/10.1145/1569901.1569943.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

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

6

Han, Aili. "An Improved DNA Solution to the Vertex Cover Problem." In 2008 Fourth International Conference on Natural Computation. IEEE, 2008. http://dx.doi.org/10.1109/icnc.2008.904.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Abu-Khzam, Faisal N., Nagiza F. Samatova, Mohamad A. Rizk, and Michael A. Langston. "The Maximum Common Subgraph Problem: Faster Solutions via Vertex Cover." In 2007 IEEE/ACS International Conference on Computer Systems and Applications. IEEE, 2007. http://dx.doi.org/10.1109/aiccsa.2007.370907.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Patel, Smit, and S. Sowmya Kamath. "Improved approximation algorithm for vertex cover problem using articulation points." In 2014 5th International Conference on Computing, Communication and Networking Technologies (ICCCNT). IEEE, 2014. http://dx.doi.org/10.1109/icccnt.2014.7093075.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

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

10

Oliveto, Pietro S., Jun He, and Xin Yao. "Analysis of population-based evolutionary algorithms for the vertex cover problem." In 2008 IEEE Congress on Evolutionary Computation (CEC). IEEE, 2008. http://dx.doi.org/10.1109/cec.2008.4631000.

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!