Efficient bounds for the stable set, vertex cover and set packing problems

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites work

A Greedy Heuristic for the Set-Covering Problem
An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
An inequality for the chromatic number of a graph
Approximation algorithms for combinatorial problems
Approximation Algorithms for the Set Covering and Vertex Cover Problems
Every planar map is four colorable. I: Discharging
Every planar map is four colorable. II: Reducibility
scientific article; zbMATH DE number 3633709 (Why is no real title available?)
scientific article; zbMATH DE number 3365308 (Why is no real title available?)
scientific article; zbMATH DE number 3043302 (Why is no real title available?)
Parallel concepts in graph theory
Some simplified NP-complete graph problems
Three short proofs in graph theory
Vertex packings: Structural properties and algorithms

Cited in

(67)

Single machine precedence constrained scheduling is a Vertex cover problem
Approximation algorithms for the weighted independent set problem in sparse graphs
On problems without polynomial kernels
Priority algorithms for graph optimization problems
Perfectness and imperfectness of unit disk graphs on triangular lattice points
Equivalent approximation algorithms for node cover
Maximum weight independent set in trees
A natural model and a parallel algorithm for approximately solving the maximum weighted independent set problem
A generalization of König-Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios
Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
A graph approximation heuristic for the vertex cover problem on planar graphs
Improved approximations for maximum independent set via approximation chains
Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
Carousel greedy: a generalized greedy algorithm with applications in optimization
The relationship between attribute reducts in rough sets and minimal vertex covers of graphs
Complexity and approximations for submodular minimization problems on two variables per inequality constraints
Why should biconnected components be identified first
An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem
Greedy -approximation algorithm for covering with arbitrary constraints and submodular cost
Approximation algorithms for finding and partitioning unit-disk graphs into co-k-plexes
Relaxing the strong triadic closure problem for edge strength inference
Approximability of open $k$-monopoly problems
Avoidable vertices and edges in graphs: existence, characterization, and applications
Minimum hitting set of interval bundles problem: computational complexity and approximability
A primal-dual approximation algorithm for \textsc{minsat}
Experimental analysis of approximation algorithms for the vertex cover and set covering problems
A simple approximation algorithm for WIS based on the approximability in $k$-partite graphs
Genus characterizes the complexity of certain graph problems: Some tight results
Runtime performances of randomized search heuristics for the dynamic weighted vertex cover problem
Vertex cover in graphs with locally few colors
Inapproximability of b-matching in k-uniform hypergraphs
Dynamic Offline Conflict-Free Coloring for Unit Disks
A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
Complexity of majority monopoly and signed domination problems
Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation
Local algorithms for bounded degree sparsifiers in sparse graphs
Improved approximations of independent sets in bounded-degree graphs
On approximation properties of the Independent set problem for degree 3 graphs
Bilu-Linial stability, certified algorithms and the independent set problem
The multi‐integer set cover and the facility terminal cover problem
The $k$-observer problem on $d$-regular graphs
Optimization problems in multiple subtree graphs
On approximating minimum vertex cover for graphs with perfect matching
Algorithm for optimal winner determination in combinatorial auctions
A probabilistic algorithm for vertex cover
Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
Greedy approximations of independent sets in low degree graphs
Independent set in $k$-claw-free graphs: conditional $\chi $-boundedness and the power of LP/SDP relaxations
Approximation algorithms for covering vertices by long paths
An approximation algorithm for covering vertices by $4^+$-paths
Distributed algorithms for covering, packing and maximum weighted matching
Ultimate greedy approximation of independent sets in subcubic graphs
Hardness and approximation of submodular minimum linear ordering problems
Iterative improvement of vertex covers
A simple LP-free approximation algorithm for the minimum weight vertex cover problem
Randomized approximation of bounded multicovering problems
Greed is good: Approximating independent sets in sparse and bounded-degree graphs
Covering vertices by 4^+-paths: a simpler local search coupled with a more delicate amortization
Analyzing the 3-path vertex cover problem in selected graph classes
An improved approximation algorithm for covering vertices by 4^+-paths
Distributed fractional local ratio and independent set approximation
Base-object location problems for base-monotone regions
Ramsey numbers and an approximation algorithm for the vertex cover problem
An edge-reduction algorithm for the vertex cover problem
Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs
On the complexity of the representation of simplicial complexes by trees
A network approach for specially structured linear programs arising in 0-1 quadratic optimization

This page was built for publication: Efficient bounds for the stable set, vertex cover and set packing problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1056763)