The k-observer problem on d-regular graphs

DOI10.1007/978-3-319-21741-3_6MaRDI QIDQ5207902zbMATH OpenOpenAlexFDO

Authors Benjamin Ries, Bernhard Schamberg, Walter Unger

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)

Recommendations

• Improved approximation algorithms for path vertex covers in regular graphs
• scientific article; zbMATH DE number 907924
• Minimum \(k\)-path vertex cover
• On the vertex \(k\)-path cover
• The connected vertex cover problem in \(k\)-regular graphs

Cites work

• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
• An attractive class of bipartite graphs
• Efficient bounds for the stable set, vertex cover and set packing problems
• Feedback from nature, an optimal distributed algorithm for \textsc{Maximal Independent Set} selection
• Minimum \(k\)-path vertex cover
• No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
• On the hardness of approximating minimum vertex cover
• On the vertex \(k\)-path cover
• On the weighted \(k\)-path vertex cover problem
• Relaxing the uniformity and independence assumptions using the concept of fractal dimension
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(3)

• scientific article; zbMATH DE number 844141 (Why is no real title available?)
• The weighted \(k\)-path vertex cover problem on series-parallel graphs
• Improved approximation algorithms for path vertex covers in regular graphs

This page was built for publication: The \(k\)-observer problem on \(d\)-regular graphs

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