Descripción: In this paper, we study the minimum sum set coloring (MSSC) problem which consists in assigning a set of x(v) positive integers to each vertex v of a graph so that the intersection of sets assigned to adjacent vertices is empty and the sum of the assigned set of numbers to each vertex of the graph is minimum. The MSSC problem occurs in two versions: non-preemptive and preemptive. We show that the MSSC problem is strongly NP-hard both in the preemptive case on trees and in the non-preemptive case in line graphs of trees. Finally, we give exact parameterized algorithms for these two versions on trees and line graphs of trees. © 2010 Elsevier B.V. All rights reserved.

Descripción: A b-coloring of a graph is a coloring such that every color class admits a vertex adjacent to at least one vertex receiving each of the colors not assigned to it. The b-chromatic number of a graph G, denoted by χb(G), is the maximum number t such that G admits a b-coloring with t colors. A graph G is b-continuous if it admits a b-coloring with t colors, for every t=χ(G),...,χb(G), and it is b-monotonic if χb(H1)<χb(H2) for every induced subgraph H1 of G, and every induced subgraph H2 of H1. In this work, we prove that P4-tidy graphs (a generalization of many classes of graphs with few induced P4s) are b-continuous and b-monotonic. Furthermore, we describe a polynomial time algorithm to compute theb-chromatic number for this class of graphs. © 2010 Elsevier B.V. All rights reserved.

Descripción: Fil:Méndez-Díaz, I. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.

Descripción: We present an approach based on integer programming formulations of the graph coloring problem. Our goal is to develop models that remove some symmetrical solutions obtained by color permutations. We study the problem from a polyhedral point of view and determine some families of facets of the 0/1-polytope associated with one of these integer programming formulations. The theoretical results described here are used to design an efficient Cutting Plane algorithm. © 2007 Elsevier B.V. All rights reserved.

Descripción: The Double Traveling Salesman Problem with Multiple Stacks is a vehicle routing problem in which pickups and deliveries must be performed in two independent networks. The items are stored in stacks and repacking is not allowed. Given a pickup and a delivery tour, the problem of checking if there exists a valid distribution of items into s stacks of size h that is consistent with the given tours, is known as Pickup and Delivery Tour Combination (PDTC) problem. In the paper, weshow that the PDTC problem canbesolved in polynomial time when the number of stacks s is fixed but the size of each stack is not. We build upon the equivalence between the PDTC problem and the bounded coloring(BC) problemonpermutation graphs: for the latter problem, s is the number of colors and h is the number of vertices that can get a same color. We show that the BC problem can be solved in polynomial time when s is a fixed constant on co-comparability graphs, a superclass of permutation graphs. To the contrary, the BC problem is known to be hard on permutation graphs when h ≥ 6 is a fixed constant, but s is unbounded. © 2011 Elsevier B.V. All rights reserved.

Descripción: In this work we study a particular way of dealing with interference in combinatorial optimization models representing wireless communication networks. In a typical wireless network, co-channel interference occurs whenever two overlapping antennas use the same frequency channel, and a less critical interference is generated whenever two overlapping antennas use adjacent channels. This motivates the formulation of the minimum-adjacency vertex coloring problem which, given an interference graph G representing the potential interference between the antennas and a set of prespecified colors/channels, asks for a vertex coloring of G minimizing the number of edges receiving adjacent colors. We propose an integer programming model for this problem and present three families of facet-inducing valid inequalities. Based on these results, we implement a branch-and-cut algorithm for this problem, and we provide promising computational results. © 2011 Elsevier B.V. All rights reserved.