Results 1 to 10 of about 2,495,395 (314)
A Survey on the k-Path Vertex Cover Problem [PDF]
Axioms, 2022 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.
Jianhua Tu
doaj +4 more sources
A Constructive Characterization of Vertex Cover Roman Trees
Discussiones Mathematicae Graph Theory, 2021 A Roman dominating function on a graph G = (V (G), E(G)) is a function f : V (G) → {0, 1, 2} satisfying the condition that every vertex u for which f (u) = 0 is adjacent to at least one vertex v for which f (v) = 2.
Martínez Abel Cabrera +2 more
doaj +3 more sources
TIVC: An Efficient Local Search Algorithm for Minimum Vertex Cover in Large Graphs. [PDF]
Sensors (Basel), 2023 The minimum vertex cover (MVC) problem is a canonical NP-hard combinatorial optimization problem aiming to find the smallest set of vertices such that every edge has at least one endpoint in the set.
Zhang Y, Wang S, Liu C, Zhu E.
europepmc +2 more sources
Self-Stabilizing Capacitated Vertex Cover Algorithms for Internet-of-Things-Enabled Wireless Sensor Networks. [PDF]
Sensors (Basel), 2022 Wireless sensor networks (WSNs) achieving environmental sensing are fundamental communication layer technologies in the Internet of Things. Battery-powered sensor nodes may face many problems, such as battery drain and software problems.
Yigit Y, Dagdeviren O, Challenger M.
europepmc +2 more sources
A faster algorithm for Vertex Cover parameterized by solution size [PDF]
Symposium on Theoretical Aspects of Computer Science, 2022 We describe a new algorithm for vertex cover with runtime $O^*(1.25284^k)$, where $k$ is the size of the desired solution and $O^*$ hides polynomial factors in the input size. This improves over previous runtime of $O^*(1.2738^k)$ due to Chen, Kanj,&Xia (
David G. Harris, N. S. Narayanaswamy
openalex +3 more sources
Improving Vertex Cover as a Graph Parameter [PDF]
Discrete Mathematics & Theoretical Computer Science, 2015 Parameterized algorithms are often used to efficiently solve NP-hard problems on graphs. In this context, vertex cover is used as a powerful parameter for dealing with graph problems which are hard to solve even when parameterized by tree-width; however,
Robert Ganian
doaj +2 more sources
Solving large Minimum Vertex Cover problems on a quantum annealer [PDF]
ACM International Conference on Computing Frontiers, 2019 We consider the minimum vertex cover problem having applications in e.g. biochemistry and network security. Quantum annealers can find the optimum solution of such NP-hard problems, given they can be embedded on the hardware. This is often infeasible due
Elijah Pelofske +2 more
openalex +3 more sources
The standard graded property for vertex cover algebras of quasi-trees [PDF]
Le Matematiche, 2008 In [5] the authors characterize the vertex cover algebras which are tandard graded. In this paper we give a simple combinatorial criterion for the standard graded property of vertex cover algebras in the case of quasi-trees.
Alexandru Costantinescu, Le Dinh Nam
doaj +5 more sources
Parameterized Streaming Algorithms for Vertex Cover [PDF]
, 2014 As graphs continue to grow in size, we seek ways to effectively process such data at scale. The model of streaming graph processing, in which a compact summary is maintained as each edge insertion/deletion is observed, is an attractive one.
Chitnis, Rajesh +3 more
core +3 more sources
An Exact Algorithm for Minimum Vertex Cover Problem
Mathematics, 2019 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 ...
Luzhi Wang +3 more
doaj +2 more sources