Equivalent approximation algorithms for node cover

DOI10.1016/0020-0190(86)90068-2MaRDI QIDQ1077934zbMATH OpenOpenAlexFDO

Authors 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

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

Cites work

• A Greedy Heuristic for the Set-Covering Problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• Approximation algorithms for combinatorial problems
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Depth-first search and the vertex cover problem
• Efficient bounds for the stable set, vertex cover and set packing problems
• scientific article; zbMATH DE number 3889282 (Why is no real title available?)
• Two-Processor Scheduling with Start-Times and Deadlines
• Vertex packings: Structural properties and algorithms

Cited in

(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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1077934)