Showing 2020 · cs.CCShow all
2 papers · 2 filters
cs.CC2020
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…
cs.CC2020
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 .…