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

DOI10.1016/0166-218X(84)90086-6zbMath0554.68026MaRDI QIDQ760210

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)

Related Items

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 ⋮ On the computational complexity of measuring global stability of banking networks ⋮ A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph ⋮ On approximation problems related to the independent set and vertex cover problems ⋮ A better constant-factor approximation for weighted dominating set in unit disk graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On approximation problems related to the independent set and vertex cover problems
• Non deterministic polynomial optimization problems and their approximations
• Depth-first search and the vertex cover problem
• Approximation algorithms for combinatorial problems
• 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
• Vertex packings: Structural properties and algorithms
• The Complexity of Near-Optimal Graph Coloring
• Two-Processor Scheduling with Start-Times and Deadlines