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

Approximation algorithms for combinatorial problems
A Greedy Heuristic for the Set-Covering Problem
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
Title not available (Why is that?)
An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
Title not available (Why is that?)
Some simplified NP-complete graph problems
Vertex packings: Structural properties and algorithms
Three short proofs in graph theory
Parallel concepts in graph theory
An inequality for the chromatic number of a graph
Title not available (Why is that?)

Cited In (63)

On the complexity of the representation of simplicial complexes by trees
A graph approximation heuristic for the vertex cover problem on planar graphs
A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
Approximation algorithms for the weighted independent set problem in sparse graphs
Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
A generalization of König-Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios
A primal-dual approximation algorithm for \textsc{minsat}
A simple approximation algorithm for WIS based on the approximability in $k$-partite graphs
Optimization problems in multiple subtree graphs
Maximum weight independent set in trees
Complexity of majority monopoly and signed domination problems
Dynamic Offline Conflict-Free Coloring for Unit Disks
Randomized approximation of bounded multicovering problems
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
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
Algorithm for optimal winner determination in combinatorial auctions
Carousel greedy: a generalized greedy algorithm with applications in optimization
Greedy approximations of independent sets in low degree graphs
Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
Bilu-Linial stability, certified algorithms and the independent set problem
Base-object location problems for base-monotone regions
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
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
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
Why should biconnected components be identified first
Distributed algorithms for covering, packing and maximum weighted matching
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
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
Genus characterizes the complexity of certain graph problems: Some tight results
A network approach for specially structured linear programs arising in 0-1 quadratic optimization
Iterative improvement of vertex covers
A simple LP-free approximation algorithm for the minimum weight vertex cover problem
Priority algorithms for graph optimization problems
Improved approximations of independent sets in bounded-degree graphs
A probabilistic algorithm for vertex cover
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
Ultimate greedy approximation of independent sets in subcubic graphs
An approximation algorithm for covering vertices by $4^+$-paths
Hardness and approximation of submodular minimum linear ordering problems
Local algorithms for bounded degree sparsifiers in sparse graphs
The multi‐integer set cover and the facility terminal cover problem
Inapproximability of $b$-matching in $k$-uniform hypergraphs

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)