In: Discrete Applied Mathematics, 2021, vol. 290, p. 17-35
In this paper we continue the systematic study of Contact graphs of Paths on a Grid (CPG graphs) initiated in Deniz et al. (2018). A CPG graph is a graph for which there exists a collection of pairwise interiorly disjoint paths on a grid in one-to-one correspondence with its vertex set such that two vertices are adjacent if and only if the corresponding paths touch at a grid-point. If every...
|
In: Algorithmica, 2015, vol. 71, no. 2, p. 354-376
|
In: Systematic Biology, 2016, vol. 65, no. 4, p. 651-661
|
In: Discrete & Computational Geometry, 2015, vol. 53, no. 4, p. 703-712
|
In: Journal of Scheduling, 2017, vol. 20, p. 391-422
Due to the limited applicability in practice of the classical job shop scheduling problem, many researchers have addressed more complex versions of this problem by including additional process features, such as time lags, setup times, and buffer limitations, and have pursued objectives that are more practically relevant than the makespan, such as total flow time and total weighted tardiness....
|
In: Discrete Mathematics, 2021, vol. 344, no. 1, p. 112169
In this work, we study the following problem: given a connected graph G, can we reduce the domination number of G by at least one using k edge contractions, for some fixed integer k > 0? We show that for k = 1 (resp. k = 2), the problem is NP-hard (resp. coNP-hard). We further prove that for k = 1, the problem is W[1]-hard parameterized by domination number plus the mim-width of the input...
|
In: Discrete Applied Mathematics, 2013, vol. 161, p. 899-908
In this paper we study the complexity of generalized versions of the firefighter problem on trees, and answer several open questions of Finbow and MacGillivray (2009) [8]. More specifically, we consider the version denoted by Max (S, b)-Fire where b ≥ 2 firefighters are allowed at each time step and the objective is to maximize the number of saved vertices that belong to S. We also study...
|
In: Discrete Applied Mathematics, 2014, vol. 178, p. 46-57
A cograph is a graph which does not contain any induced path on four vertices. In this paper, we characterize those cographs that are intersection graphs of paths on a grid in the following two cases: (i) the paths on the grid all have at most one bend and the intersections concern edges (→ B1-EPG); (ii) the paths on the grid are not bended and the intersections concern vertices (→...
|
In: European Journal of Operational Research, 2015, vol. 240, no. 2, p. 307-314
In this paper we present the Selective Graph Coloring Problem, a generalization of the standard graph col-oring problem as well as several of its possible applications. Given a graph with a partition of its vertex set into several clusters, we want to select one vertex per cluster such that the chromatic number of the subgraph induced by the selected vertices is minimum. This problem appeared...
|
In: European Journal of Operational Research, 2011, vol. 210, no. 2, p. 169-175
Given a graph G =(V, E), a satisfying bisection of G is a partition of the vertex set V into two sets V1, V2, such that |V1| = |V2|, and such that every vertex v in V has at least as many neighbors in its own set as in the other set. The problem of deciding whether a graph G admits such a partition is NP-complete. In Bazgan et al. (2008) [C. Bazgan, Z. Tuza, D. Vanderpooten, Approximation of...
|