A linear-time approximation algorithm for the weighted vertex cover problem
From MaRDI portal
Publication:3910012
DOI10.1016/0196-6774(81)90020-1zbMath0459.68033OpenAlexW2064600658WikidataQ61632373 ScholiaQ61632373MaRDI QIDQ3910012
No author found.
Publication date: 1981
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(81)90020-1
Graph theory (including graph drawing) in computer science (68R10) Discrete mathematics in relation to computer science (68R99)
Related Items
Equivalent approximation algorithms for node cover, Vertex cover meets scheduling, A graph approximation heuristic for the vertex cover problem on planar graphs, An experimental comparison of three heuristics for the WVCP, Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique, A fast approximation algorithm for the multicovering problem, Design of Dynamic Algorithms via Primal-Dual Method, On residual approximation in solution extension problems, On the multi-radius cover problem, A Water-Filling Primal-Dual Algorithm for Approximating NonLinear Covering Problems, A survey on combinatorial optimization in dynamic environments, Dynamic algorithms via the primal-dual method, A reduction tree approach for the discrete time/cost trade-off problem, Resource allocation problem under single resource assignment, A primal-dual approximation algorithm for partial vertex cover: Making educated guesses, A primal-dual approximation algorithm for \textsc{minsat}, New primal-dual algorithms for Steiner tree problems, A general approximation method for bicriteria minimization problems, Runtime performances of randomized search heuristics for the dynamic weighted vertex cover problem, An efficient fixed-parameter algorithm for 3-hitting set, Query-competitive sorting with uncertainty, Rounding algorithms for covering problems, Primal-Dual Schema for Capacitated Covering Problems, Combinatorial model and bounds for target set selection, Competitive vertex recoloring. (Online disengagement), PTAS for minimum weighted connected vertex cover problem with \(c\)-local condition in unit disk graphs, Computing connected-\(k\)-subgraph cover with connectivity requirement, On Residual Approximation in Solution Extension Problems, Distributed half-integral matching and beyond, On the approximability and hardness of minimum topic connected overlay and its special instances, Approximation of the quadratic set covering problem, An approximation algorithm for \(P\)-prize-collecting set cover problem, Online and Approximate Network Construction from Bounded Connectivity Constraints, A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem, Distributed half-integral matching and beyond, A unified approach to approximating partial covering problems, Online and approximate network construction from bounded connectivity constraints, Improved Algorithm for Resource Allocation Problems, Approximability of sparse integer programs, Unnamed Item, Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost, The vertex cover \(P_3\) problem in cubic graphs, Static Routing in Stochastic Scheduling: Performance Guarantees and Asymptotic Optimality, A primal-dual approximation algorithm for the vertex cover \(P^3\) problem, Approximation algorithms for hitting objects with straight lines, Iterative partial rounding for vertex cover with hard capacities, Capacitated Domination Problem, Approximation algorithms for partially covering with edges, A fixed-parameter algorithm for the vertex cover \(P_3\) problem, Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover, Distributed algorithms for covering, packing and maximum weighted matching, Complexity of the repeaters allocating problem, LP-based covering games with low price of anarchy, Heuristics for automated knowledge source integration and service composition, Online budgeted maximum coverage, Efficient algorithm for the vertex cover \(P_k\) problem on cacti, Rounding to an integral program, A simple LP-free approximation algorithm for the minimum weight vertex cover problem, \(O(f)\) bi-criteria approximation for capacitated covering with hard capacities, Admission control with advance reservations in simple networks, Preserving approximation in the min-weighted set cover problem, Primal-dual approximation algorithms for integral flow and multicut in trees, A bounded approximation for the minimum cost 2-sat problem, The minimum substring cover problem, A new fixed point approach for stable networks and stable marriages, Combination of parallel machine scheduling and vertex cover, Capacitated domination problem, Approximation algorithms for art gallery problems in polygons, Approximating the dense set-cover problem, New complexity results for the \(k\)-covers problem, Minimum vertex cover in rectangle graphs, Experimental analysis of approximation algorithms for the vertex cover and set covering problems, The multi‐integer set cover and the facility terminal cover problem, The Minimum Substring Cover Problem, Hitting Forbidden Minors: Approximation and Kernelization, On the primer selection problem in polymerase chain reaction experiments, The set covering problem revisited: an empirical study of the value of dual information, Approximation algorithm for stochastic set cover problem, Domination in Geometric Intersection Graphs, Approximating the discrete time-cost tradeoff problem with bounded depth, Approximating the discrete time-cost tradeoff problem with bounded depth, Approximation algorithms for the partition vertex cover problem, A randomised approximation algorithm for the hitting set problem, Primal-dual schema for capacitated covering problems, Distributed set cover approximation: Primal-dual with optimal locality, On approximation problems related to the independent set and vertex cover problems, Efficient approximation algorithms for maximum coverage with group budget constraints, The power of the weighted sum scalarization for approximating multiobjective optimization problems, Efficient Online Linear Optimization with Approximation Algorithms, Exploring further advantages in an alternative formulation for the set covering problem, Pareto optimality and a class of set covering heuristics, Clustering heuristics for set covering, On the Parameterized Approximability of Contraction to Classes of Chordal Graphs, Network flow and 2-satisfiability
