Results 231 to 240 of about 17,985 (261)
Some of the next articles are maybe not open access.
A list heuristic for vertex cover
Operations Research Letters, 2007A class of approximation algorithms for the minimum vertex cover problem for graphs is studied. These algorithms, called list heuristics, handle the vertices in a given static order based on the degree sequence. The authors prove an approximation ratio of at most \(\sqrt{\Delta}/2+\frac{3}{2}\) for a nonincreasing degree sequence, and show that no ...
David Avis, Tomokazu Imamura
openaire +2 more sources
Multiple vertex coverings by cliques
Journal of Graph Theory, 2004For positive integers \(m_1,\dots,m_k\), let \(f(m_1,\dots,m_k)\) be the minimum order of a graph whose edges can be colored with \(k\) colors such that every vertex is in a clique of cardinality \(m_i\), all of whose edges have the \(i\)th color for all \(i=1,2,\dots,k\). The value for \(k=2\) was determined by \textit{R. C. Entringer} et al. [J Graph
Wayne Goddard, Michael A. Henning
openaire +2 more sources
Paths, Flowers and Vertex Cover
2011It is well known that in a bipartite (and more generally in a Konig) graph, the size of the minimum vertex cover is equal to the size of the maximum matching. We first address the question whether (and if not when) this property still holds in a Konig graph if we insist on forcing one of the two vertices of some of the matching edges in the vertex ...
Venkatesh Raman 0001 +2 more
openaire +1 more source
Solving #SAT Using Vertex Covers
Acta Informatica, 2006zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Naomi Nishimura +2 more
openaire +2 more sources
Extended formulations for vertex cover
Operations Research Letters, 2016zbMATH Open Web Interface contents unavailable due to conflicting licenses.
openaire +2 more sources
Evolutionary algorithms for vertex cover
1998This paper reports work investigating various evolutionary approaches to vertex cover (VC), a well-known NP-Hard optimization problem. Central to each of the algorithms is a novel encoding scheme for VC and related problems that treats each chromosome as a binary decision diagram.
openaire +1 more source
The Minimum Generalized Vertex Cover Problem
ACM Transactions on Algorithms, 2003Let G = ( V , E ) be an undirected graph, with three numbers d 0 ( e ) ≥ d 1 ( e ) ≥ d 2 ( e
Refael Hassin, Asaf Levin
openaire +1 more source
On the vertex covering sets and vertex cover polynomials of square of paths
IOSR Journal of Mathematics, 2013Let G be a graph of order n with no isolated vertex. Let (G,i) be the family of vertex covering sets in G with cardinality i and let c(G, i) = | |. The polynomial C(G, x) = c(G, i) is called the vertex cover polynomial of G. In this paper, we obtain some properties of the polynomial C( ) and its coefficients.
openaire +1 more source
Mortal and eternal vertex covers
2016Summary: A vertex cover of a graph \(G = (V, E)\) is a subset \(S\subseteq V\) such that every edge is incident with at least one vertex in 5, and \(\alpha(G)\) is the cardinality of a smallest vertex cover. For a given vertex cover 5, a defense by \(S\) to an attack on an edge \(e = {vw}\) where \(v\in S\), is a one-to-one function \(f: S\to V\), such
Anderson, Mark +4 more
openaire +1 more source
A theorem on the approximation of set cover and vertex cover
1991An approximation result is given, connecting two well known combinatorial problems, the Set Cover and the Vertex Cover. This result constitutes an improvement of the existing ratio for the latter, on a large and intuitive class of graphs, provided that an approximation algorithm exists for the former.
openaire +1 more source