Results 241 to 249 of about 142,209 (249)
Some of the next articles are maybe not open access.
Refined memorization for vertex cover
Information Processing Letters, 2004Memorization is a technique which allows to speed up exponential recursive algorithms at the cost of an exponential space complexity. This technique already leads to the currently fastest algorithm for fixed-parameter vertex cover, whose time complexity is O(1.2832^kk^1^.^5+kn), where n is the number of nodes and k is the size of the vertex cover.
Fabrizio Grandoni, L. Sunil Chandran
openaire +3 more sources
Maximum Minimal Vertex Cover Parameterized by Vertex Cover
SIAM Journal on Discrete Mathematics, 2015The parameterized complexity of problems is often studied with respect to the size of their optimal solutions. However, for a maximization problem, the size of the optimal solution can be very large, rendering algorithms parameterized by it inefficient. Therefore, we suggest studying the parameterized complexity of maximization problems with respect to
openaire +3 more sources
On approximation of max-vertex-cover
European Journal of Operational Research, 2002zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Jiawei Zhang +3 more
openaire +2 more sources
Algorithmica, 2015
We consider a hybrid two-stage optimization problem that generalizes two classic combinatorial optimization problems: (i) weighted vertex cover in graphs, and (ii) makespan minimization in multiprocessor scheduling. An instance specifies a machine environment, a set of jobs, and an undirected graph over the jobs.
Asaf Levin +2 more
openaire +2 more sources
We consider a hybrid two-stage optimization problem that generalizes two classic combinatorial optimization problems: (i) weighted vertex cover in graphs, and (ii) makespan minimization in multiprocessor scheduling. An instance specifies a machine environment, a set of jobs, and an undirected graph over the jobs.
Asaf Levin +2 more
openaire +2 more sources
On the vertex covering sets and vertex cover polynomials of square of ladder graph
Journal of Discrete Mathematical Sciences and Cryptography, 2016AbstractLet G be a graph of order n with no isolated vertex. A vertex covering of the graph G is a set of vertices such that every edge of the graph is incident to atleast one vertex of the set. Let C(G, i) be the family of vertex covering sets in G with cardinality ‘i’ and let c(G, i) = | C(G, i) |. The polynomial is called the vertex cover polynomial
A. Vijayan, T. S. Ida Helan
openaire +2 more sources
Improved approximation of maximum vertex cover
Operations Research Letters, 2006zbMATH Open Web Interface contents unavailable due to conflicting licenses.
GALLUCCIO A., NOBILI, Paolo
openaire +5 more sources
A probabilistic algorithm for vertex cover
Theoretical Computer Science, 2022shaked mamana, Daniel Berend
openaire +1 more source
Iterative improvement of vertex covers
Information Processing Letters, 1995openaire +3 more sources