1 citations · 1 across the 11 of their papers we have counts for
4 papers · 1 filter
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…
A Unifying Model for Locally Constrained Spanning Tree Problems
Luiz Alberto do Carmo Viana, Manoel Campêlo, Ignasi Sau +1
Given a graph and a digraph whose vertices are the edges of , we investigate the problem of finding a spanning tree of that satisfies the constraints imposed by .…
Coloring Problems on Bipartite Graphs of Small Diameter
Victor A. Campos, Guilherme C. M. Gomes, Allen Ibiapina +3
We investigate a number of coloring problems restricted to bipartite graphs with bounded diameter. First, we investigate the -List Coloring, List -Coloring, and -Precolori…
Edge-Disjoint Branchings in Temporal Graphs
Victor Campos, Raul Lopes, Andrea Marino +1
A temporal digraph is a triple where is a digraph, is a function on that tells us the timestamps when a vertex is active, and is a functio…