7 citations · 9 across the 13 of their papers we have counts for
13 papers
Convex Recoloring of General Graphs: Formulations, Polyhedra, and Computational Experiments
Boyue Lin, Phablo F. S. Moura, Roel Leus
A vertex coloring of a graph is convex if the vertices of each color induce a connected subgraph. In the convex recoloring problem (CR), the goal is to find a convex coloring while…
Covering and packing mixed-integer linear programs with a fixed number of constraints: Approximation and convex hull
Kobe Grobben, Phablo F. S. Moura, Hande Yaman
This paper presents an algorithmic study of a class of covering mixed-integer linear programming problems which encompasses classic cover problems, including multidimensional knaps…
Balanced connected partitions of edge-weighted graphs: Hardness and solving methods
Morteza Davari, Phablo F. S. Moura, Hande Yaman
The balanced connected -partition problem (\textsc{bcp}) is a classic problem, which consists in partitioning the set of vertices of a vertex-weighted connected graph into a col…
On the connected (sub)partition polytope
Phablo F. S. Moura, Hande Yaman, Roel Leus
Let be a positive integer and let be a graph with vertices. A connected -subpartition of is a collection of pairwise disjoint sets (a.k.a. classes) of vertic…
Compact formulations and valid inequalities for parallel machine scheduling with conflicts
Phablo F. S. Moura, Roel Leus, Hande Yaman
The problem of scheduling conflicting jobs on parallel machines consists in assigning a set of jobs to a set of machines so that no two conflicting jobs are allocated to the same m…
Polyhedral approach to weighted connected matchings in general graphs
Phillippe Samer, Phablo F. S. Moura
A connected matching in a graph G consists of a set of pairwise disjoint edges whose covered vertices induce a connected subgraph of G. While finding a connected matching of maximu…
Approximations for the Steiner Multicycle Problem
Cristina G. Fernandes, Carla N. Lintzmayer, Phablo F. S. Moura
The Steiner Multicycle problem consists of, given a complete graph, a weight function on its vertices, and a collection of pairwise disjoint non-unitary sets called terminal sets,…
Seymour's Second Neighborhood Conjecture for orientations of (pseudo)random graphs
Fábio Botler, Phablo F. S. Moura, Tássio Naia
Seymour's Second Neighborhood Conjecture (SNC) states that every oriented graph contains a vertex whose second neighborhood is as large as its first neighborhood. We investigate th…
Approximation and parameterized algorithms to find balanced connected partitions of graphs
Phablo F. S. Moura, Matheus J. Ota, Yoshiko Wakabayashi
Partitioning a connected graph into ~vertex-disjoint connected subgraphs of similar (or given) orders is a classical problem that has been intensively investigated since late se…
Polyhedral study of the Convex Recoloring problem
Manoel Campêlo, Phablo F. S. Moura, Joel C. Soares
A coloring of the vertices of a connected graph is convex if each color class induces a connected subgraph. We address the convex recoloring (CR) problem defined as follows. Given…
Integer Programming Approaches to Balanced Connected -Partition
Flávio K. Miyazawa, Phablo F. S. Moura, Matheus J. Ota +1
We address the problem of partitioning a vertex-weighted connected graph into connected subgraphs that have similar weights, for a fixed integer . This problem, known…
Subdivisions in digraphs of large out-degree or large dichromatic number
Pierre Aboulker, Nathann Cohen, Fréderic Havet +3
In 1985, Mader conjectured the existence of a function such that every digraph with minimum out-degree at least contains a subdivision of the transitive tournament of or…
Optimal k-fold colorings of webs and antiwebs
Manoel Campêlo, Ricardo C. Corrêa, Phablo F. S. Moura +1
A k-fold x-coloring of a graph is an assignment of (at least) k distinct colors from the set {1, 2, ..., x} to each vertex such that any two adjacent vertices are assigned disjoint…