1 citations · 1 across the 3 of their papers we have counts for
3 papers
Edge Intersection Graphs of Paths on a Triangular Grid
Vitor T. F. de Luca, María Pía Mazzoleni, Fabiano S. Oliveira +2
We introduce a new class of intersection graphs, the edge intersection graphs of paths on a triangular grid, called EPGt graphs. We show similarities and differences from this new…
MaxCut on Permutation Graphs is NP-complete
Celina M. H. de Figueiredo, Alexsander A. de Melo, Fabiano S. Oliveira +1
In this paper, we prove that the MaxCut problem is NP-complete on permutation graphs, settling a long-standing open problem that appeared in the 1985 column of the "Ongoing Guide t…
Maximum cut on interval graphs of interval count four is NP-complete
Celina M. H. de Figueiredo, Alexsander A. de Melo, Fabiano S. Oliveira +1
The computational complexity of the MaxCut problem restricted to interval graphs has been open since the 80's, being one of the problems proposed by Johnson on his Ongoing Guide to…