Efficient bounds for the stable set, vertex cover and set packing problems
From MaRDI portal
Publication:1056763
DOI10.1016/0166-218X(83)90080-XzbMath0523.05055MaRDI QIDQ1056763
Publication date: 1983
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
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)
Related Items (58)
Equivalent approximation algorithms for node cover ⋮ A graph approximation heuristic for the vertex cover problem on planar graphs ⋮ An edge-reduction algorithm for the vertex cover problem ⋮ Improved approximations of independent sets in bounded-degree graphs ⋮ On approximation properties of the Independent set problem for degree 3 graphs ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation ⋮ Maximum weight independent set in trees ⋮ Genus characterizes the complexity of certain graph problems: Some tight results ⋮ Carousel greedy: a generalized greedy algorithm with applications in optimization ⋮ Minimum hitting set of interval bundles problem: computational complexity and approximability ⋮ A primal-dual approximation algorithm for \textsc{minsat} ⋮ Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs ⋮ Improved approximations for maximum independent set via approximation chains ⋮ Runtime performances of randomized search heuristics for the dynamic weighted vertex cover problem ⋮ A natural model and a parallel algorithm for approximately solving the maximum weighted independent set problem ⋮ A novel parameterised approximation algorithm for \textsc{minimum vertex cover} ⋮ Complexity of majority monopoly and signed domination problems ⋮ A probabilistic algorithm for vertex cover ⋮ An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem ⋮ On the complexity of the representation of simplicial complexes by trees ⋮ Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost ⋮ Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes ⋮ Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs ⋮ Distributed algorithms for covering, packing and maximum weighted matching ⋮ Iterative improvement of vertex covers ⋮ A network approach for specially structured linear programs arising in 0-1 quadratic optimization ⋮ A simple LP-free approximation algorithm for the minimum weight vertex cover problem ⋮ Relaxing the strong triadic closure problem for edge strength inference ⋮ Recoverable Values for Independent Sets ⋮ Vertex Cover in Graphs with Locally Few Colors ⋮ Randomized approximation of bounded multicovering problems ⋮ Greed is good: Approximating independent sets in sparse and bounded-degree graphs ⋮ The relationship between attribute reducts in rough sets and minimal vertex covers of graphs ⋮ Optimization problems in multiple subtree graphs ⋮ Unnamed Item ⋮ On approximating minimum vertex cover for graphs with perfect matching ⋮ Experimental analysis of approximation algorithms for the vertex cover and set covering problems ⋮ The multi‐integer set cover and the facility terminal cover problem ⋮ Dynamic Offline Conflict-Free Coloring for Unit Disks ⋮ Algorithm for optimal winner determination in combinatorial auctions ⋮ The k-Observer Problem on d-regular Graphs ⋮ Complexity and approximations for submodular minimization problems on two variables per inequality constraints ⋮ Why should biconnected components be identified first ⋮ Inapproximability of b-Matching in k-Uniform Hypergraphs ⋮ Universal hinge patterns for folding strips efficiently into any grid polyhedron ⋮ Approximability of open \(k\)-monopoly problems ⋮ Base-object location problems for base-monotone regions ⋮ Single machine precedence constrained scheduling is a Vertex cover problem ⋮ Avoidable vertices and edges in graphs: existence, characterization, and applications ⋮ Approximation algorithms for the weighted independent set problem in sparse graphs ⋮ Ramsey numbers and an approximation algorithm for the vertex cover problem ⋮ A generalization of König-Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios ⋮ On problems without polynomial kernels ⋮ Priority algorithms for graph optimization problems ⋮ Perfectness and imperfectness of unit disk graphs on triangular lattice points ⋮ A simple approximation algorithm for WIS based on the approximability in \(k\)-partite graphs ⋮ Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations ⋮ Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for combinatorial problems
- Three short proofs in graph theory
- Some simplified NP-complete graph problems
- Every planar map is four colorable. I: Discharging
- Every planar map is four colorable. II: Reducibility
- Parallel concepts in graph theory
- A Greedy Heuristic for the Set-Covering Problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Vertex packings: Structural properties and algorithms
- An inequality for the chromatic number of a graph
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
This page was built for publication: Efficient bounds for the stable set, vertex cover and set packing problems
