Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00621
Improved (In)Approximability Bounds for dScattered Set
Vol. 27, no. 3, pp. 219238, 2023. Regular paper.
Abstract In the $d$${\rm S{\small CATTERED}\;S{\small ET}}$ problem we are asked to select at least $k$ vertices of a given graph, so that the distance between any pair is at least $d$. We study the problem's (in)approximability and offer improvements and extensions of known results for ${\rm I{\small NDEPENDENT}\;S{\small ET}}$, of which it is a generalization. Specifically, we show:
This work is licensed under the terms of the CCBY license.

Submitted: June 2020.
Reviewed: February 2021.
Revised: February 2021.
Accepted: April 2023.
Final: April 2023.
Published: May 2023.
Communicated by
Guy Even

Journal Supporters
