14 citations · 64 across the 19 of their papers we have counts for
3 papers · 1 filter
Shifting coresets: obtaining linear-time approximations for unit disk graphs and other geometric intersection graphs
Guilherme D. da Fonseca, Vinícius G. Pereira de Sá, Celina M. H. de Figueiredo
Numerous approximation algorithms for problems on unit disk graphs have been proposed in the literature, exhibiting a sharp trade-off between running times and approximation ratios…
Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
Guilherme D. da Fonseca, Celina M. H. de Figueiredo, Vinícius G. P. de Sá +1
A unit disk graph is the intersection graph of n congruent disks in the plane. Dominating sets in unit disk graphs are widely studied due to their application in wireless ad-hoc ne…
Complexity dichotomy on partial grid recognition
Vinícius G. P. de Sá, Guilherme D. da Fonseca, Raphael Machado +1
Deciding whether a graph can be embedded in a grid using only unit-length edges is NP-complete, even when restricted to binary trees. However, it is not difficult to devise a numbe…