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

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

Cites work

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?)
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 the Set Covering and Vertex Cover Problems
Approximation algorithms for combinatorial problems
Every planar map is four colorable. I: Discharging
Every planar map is four colorable. II: Reducibility
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

(63)

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

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)