19 citations · 50 across the 7 of their papers we have counts for
3 papers · 1 filter
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…
Biclique-colouring verification complexity and biclique-colouring power graphs
Hélio B. Macêdo Filho, Simone Dantas, Raphael C. S. Machado +1
Biclique-colouring is a colouring of the vertices of a graph in such a way that no maximal complete bipartite subgraph with at least one edge is monochromatic. We show that it is c…
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…