Open Access
Open access
Springer Nature
Lecture Notes in Computer Science
,  pages 300-313

Forest Covers and Bounded Forest Covers

Publication type: Book Chapter
Publication date: 2025-02-06
Springer Nature
scimago Q2
SJR: 0.352
CiteScore: 2.4
Impact factor: —
ISSN: 03029743, 16113349, 18612075, 18612083
Abstract
We study approximation algorithms for the forest cover and bounded forest cover problems. A probabilistic $$2+\epsilon $$ approximation algorithm for the forest cover problem is given using the method of dual fitting. A deterministic algorithm with a 2-approximation ratio that rounds the optimal solution to a linear program is given next. The 2-approximation for the forest cover is then used to give a 6-approximation for the bounded forest cover problem. The use of the probabilistic method to develop the $$2+\epsilon $$ approximation algorithm may be of independent interest.
Found 

Are you a researcher?

Create a profile to get free access to personal recommendations for colleagues and new articles.
Metrics
0
Share
Cite this
GOST |
Cite this
GOST Copy
GAUR D. R. et al. Forest Covers and Bounded Forest Covers // Lecture Notes in Computer Science. 2025. pp. 300-313.
GOST all authors (up to 50) Copy
GAUR D. R., Gorain B., Patra S., Singh R. R. Forest Covers and Bounded Forest Covers // Lecture Notes in Computer Science. 2025. pp. 300-313.
RIS |
Cite this
RIS Copy
TY - GENERIC
DO - 10.1007/978-3-031-82670-2_22
UR - https://link.springer.com/10.1007/978-3-031-82670-2_22
TI - Forest Covers and Bounded Forest Covers
T2 - Lecture Notes in Computer Science
AU - GAUR, DAYA RAM
AU - Gorain, Barun
AU - Patra, Shaswati
AU - Singh, Rishi Ranjan
PY - 2025
DA - 2025/02/06
PB - Springer Nature
SP - 300-313
SN - 0302-9743
SN - 1611-3349
SN - 1861-2075
SN - 1861-2083
ER -
BibTex
Cite this
BibTex (up to 50 authors) Copy
@incollection{2025_GAUR,
author = {DAYA RAM GAUR and Barun Gorain and Shaswati Patra and Rishi Ranjan Singh},
title = {Forest Covers and Bounded Forest Covers},
publisher = {Springer Nature},
year = {2025},
pages = {300--313},
month = {feb}
}