Equivalent approximation algorithms for node cover

DOI10.1016/0020-0190(86)90068-2zbMath0595.68058OpenAlexW1982761864MaRDI QIDQ1077934

Dan Gusfield, Leonard Pitt

Publication date: 1986

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(86)90068-2

zbMATH Keywords

graph algorithmnode covering

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items (3)

A bounded approximation for the minimum cost 2-sat problem ⋮ A new fixed point approach for stable networks and stable marriages ⋮ Network flow and 2-satisfiability

Cites Work

• Unnamed Item
• Efficient bounds for the stable set, vertex cover and set packing problems
• 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
• Two-Processor Scheduling with Start-Times and Deadlines

This page was built for publication: Equivalent approximation algorithms for node cover