On approximation problems related to the independent set and vertex cover problems
From MaRDI portal
Publication:760210
DOI10.1016/0166-218X(84)90086-6zbMATH Open0554.68026MaRDI QIDQ760210FDOQ760210
Reuven Bar-Yehuda, Shlomo Moran
Publication date: 1984
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Recommendations
- On the complexity of approximating the independent set problem
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- On the hardness of approximating minimum vertex cover
- The approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems
- On the hardness of approximating minimization problems
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Title not available (Why is that?)
- Approximation algorithms for combinatorial problems
- A Greedy Heuristic for the Set-Covering Problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Title not available (Why is that?)
- Depth-first search and the vertex cover problem
- A linear-time approximation algorithm for the weighted vertex cover problem
- Vertex packings: Structural properties and algorithms
- Title not available (Why is that?)
- Title not available (Why is that?)
- Two-Processor Scheduling with Start-Times and Deadlines
- Non deterministic polynomial optimization problems and their approximations
- The Complexity of Near-Optimal Graph Coloring
- On approximation problems related to the independent set and vertex cover problems
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (14)
- A graph approximation heuristic for the vertex cover problem on planar graphs
- Title not available (Why is that?)
- Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms
- Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa
- A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
- Parallel algorithm for minimum partial dominating set in unit disk graph
- Title not available (Why is that?)
- A better constant-factor approximation for weighted dominating set in unit disk graph
- On approximation properties of the independent set problem for low degree graphs
- Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph
- On the computational complexity of measuring global stability of banking networks
- On approximation problems related to the independent set and vertex cover problems
- Title not available (Why is that?)
- On locally optimal independent sets and vertex covers
This page was built for publication: On approximation problems related to the independent set and vertex cover problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q760210)
