Results 21 to 30 of about 166,020 (278)
An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 Given a graph $G=(V,E)$ and a positive integer $t\geq2$, the task in the vertex cover $P_t$ ($VCP_t$) problem is to find a minimum subset of vertices $F\subseteq V$ such that every path of order $t$ in $G$ contains at least one vertex from $F$.
Zongwen Bai, Jianhua Tu, Yongtang Shi
doaj +1 more source
Verified Approximation Algorithms [PDF]
Logical Methods in Computer Science, 2022 We present the first formal verification of approximation algorithms for NP-complete optimization problems: vertex cover, independent set, set cover, center selection, load balancing, and bin packing.
Robin Eßmann +3 more
doaj +1 more source
Vertex Cover Kernelization Revisited: Upper and Lower Bounds for a Refined Parameter [PDF]
, 2012 An important result in the study of polynomial-time preprocessing shows that there is an algorithm which given an instance (G,k) of Vertex Cover outputs an equivalent instance (G',k') in polynomial time with the guarantee that G' has at most 2k' vertices
A. Schrijver +43 more
core +2 more sources
Towards Distributed Two-Stage Stochastic Optimization [PDF]
, 2020 The weighted vertex cover problem is concerned with selecting a subset of the vertices that covers a target set of edges with the objective of minimizing the total cost of the selected vertices.
Emek, Yuval +2 more
core +1 more source
Truly non-trivial graphoidal graphs
AKCE International Journal of Graphs and Combinatorics, 2022 A graphoidal cover of a graph G is a collection [Formula: see text] of non-trivial paths in G, which are not necessarily open, such that every vertex of G is an internal vertex of at most one path in [Formula: see text] and every edge of G is in exactly ...
Rajesh Singh, Purnima Gupta, S. Arumugam
doaj +1 more source
Theoretical Computer Science, 2005 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Demange, Marc, Paschos, Vangelis
openaire +2 more sources
Dimension Incremental Feature Selection Approach for Vertex Cover of Hypergraph Using Rough Sets
IEEE Access, 2018 The minimum vertex cover problem is a well-known optimization problem; it has been used in a wide variety of applications. This paper focuses on rough set-based approach for the minimum vertex cover problem of the dynamic and static hypergraphs.
Qian Zhou, Xiaolin Qin, Xiaojun Xie
doaj +1 more source
Determining the Solution Space of Vertex-Cover by Interactions and Backbones [PDF]
, 2012 To solve the combinatorial optimization problems especially the minimal Vertex-cover problem with high efficiency, is a significant task in theoretical computer science and many other subjects.
B. Bollobàs +12 more
core +1 more source
Domination in graphoidally covered graphs: Least-kernel graphoidal graphs-II
AKCE International Journal of Graphs and Combinatorics, 2018 Given a graph , not necessarily finite, a graphoidal cover of means a collection of non-trivial paths in called -edges, which are not necessarily open (not necessarily finite), such that every vertex of is an internal vertex of at most one path in and ...
Purnima Gupta, Rajesh Singh
doaj +2 more sources
Squarefree Vertex Cover Algebras [PDF]
Communications in Algebra, 2013 In this paper we introduce squarefree vertex cover algebras. We study the question when these algebras coincide with the ordinary vertex cover algebras and when these algebras are standard graded. In this context we exhibit a duality theorem for squarefree vertex cover algebras.
Bayati, Shamila, Rahmati, Farhad
openaire +2 more sources