The k-Observer Problem on d-regular Graphs

DOI10.1007/978-3-319-21741-3_6zbMath1428.68225OpenAlexW2281477993MaRDI QIDQ5207902

Benjamin Ries, Walter Unger, Bernhard Schamberg

Publication date: 14 January 2020

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-21741-3_6

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items

Unnamed Item ⋮ Improved approximation algorithms for path vertex covers in regular graphs

Cites Work

• Unnamed Item
• On the weighted \(k\)-path vertex cover problem
• On the hardness of approximating minimum vertex cover
• Efficient bounds for the stable set, vertex cover and set packing problems
• Relaxing the uniformity and independence assumptions using the concept of fractal dimension
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• Minimum \(k\)-path vertex cover
• On the vertex \(k\)-path cover
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
• An attractive class of bipartite graphs
• Feedback from nature
• No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ