5 papers
On the arboreal jump number of a poset
Evellyn S. Cavalcante, Sebastián Urrutia, Vinicius F. dos Santos
A jump is a pair of consecutive elements in an extension of a poset which are incomparable in the original poset. The arboreal jump number is an NP-hard problem that aims to find a…
On the Computational Complexity of the Strong Geodetic Recognition Problem
Carlos V. G. C. Lima, Vinicius F. dos Santos, João H. G. Sousa +1
A strong geodetic set of a graph~ is a vertex set~ in which it is possible to cover all the remaining vertices of~ by assigning a uniqu…
The matching relaxation for a class of generalized set partitioning problems
Phillippe Samer, Evellyn Cavalcante, Sebastián Urrutia +1
This paper introduces a discrete relaxation for the class of combinatorial optimization problems which can be described by a set partitioning formulation under packing constraints.…
A Decomposition Approach to Solve The Quay Crane Scheduling Problem
Afonso Sampaio, Sebastián Urrutia, Johan Oppen
In this work we propose a decomposition approach to solve the quay crane scheduling problem. This is an important maritime transportation problem faced in container terminals where…
An effective decomposition approach and heuristics to generate spanning trees with a small number of branch vertices
Rafael A. Melo, Phillippe Samer, Sebastián Urrutia
Given a graph , the minimum branch vertices problem consists in finding a spanning tree of minimizing the number of vertices with degree greater than two. W…