The k-observer problem on d-regular graphs

DOI10.1007/978-3-319-21741-3_6zbMATH Open1428.68225OpenAlexW2281477993MaRDI QIDQ5207902FDOQ5207902

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

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

Mathematics Subject Classification ID

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

Cites Work

• 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 \)
• Title not available (Why is that?)
• On the weighted \(k\)-path vertex cover problem
• On the hardness of approximating minimum vertex cover
• Relaxing the uniformity and independence assumptions using the concept of fractal dimension
• Feedback from nature
• Efficient bounds for the stable set, vertex cover and set packing problems
• An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
• An attractive class of bipartite graphs
• No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ

Cited In (3)

• Improved approximation algorithms for path vertex covers in regular graphs
• Title not available (Why is that?)
• Title not available (Why is that?)

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)