On approximation problems related to the independent set and vertex cover problems

DOI10.1016/0166-218X(84)90086-6MaRDI QIDQ760210zbMATH OpenFDO

Authors Reuven Bar-Yehuda, Shlomo Moran

Publication date 1984

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

complexity of approximation algorithmsMaximum Independent SetMinimum Vertex Cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

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

Cites work

• scientific article; zbMATH DE number 3889282 (Why is no real title available?)
• scientific article; zbMATH DE number 3688740 (Why is no real title available?)
• scientific article; zbMATH DE number 3750313 (Why is no real title available?)
• scientific article; zbMATH DE number 3482375 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Greedy Heuristic for the Set-Covering Problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Approximation algorithms for combinatorial problems
• Depth-first search and the vertex cover problem
• Non deterministic polynomial optimization problems and their approximations
• On approximation problems related to the independent set and vertex cover problems
• The Complexity of Near-Optimal Graph Coloring
• Two-Processor Scheduling with Start-Times and Deadlines
• Vertex packings: Structural properties and algorithms

Cited in

(14)

• On locally optimal independent sets and vertex covers
• A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
• A graph approximation heuristic for the vertex cover problem on planar graphs
• Parallel algorithm for minimum partial dominating set in unit disk graph
• Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph
• Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
• scientific article; zbMATH DE number 1405687 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 845765 (Why is no real title available?)
• On approximation problems related to the independent set and vertex cover problems
• Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa
• On the computational complexity of measuring global stability of banking networks
• scientific article; zbMATH DE number 7378380 (Why is no real title available?)

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)