Search

Abstract: An equitable -coloring of a graph is defined by a partition of its vertices into disjoint stable subsets, such that the difference between the cardinalities of any two subsets is at most one. The equitable coloring problem consists of finding the minimum value of such that a given graph can be equitably -colored. We present two new integer programming formulations based on representatives for the equitable coloring problem. We propose a primal constructive heuristic, branching strategies, and the first branch-and-cut algorithm in the literature of the equitable coloring problem. The computational experiments were carried out on randomly generated graphs, DIMACS graphs, and other graphs from the literature. [Copyright &y& Elsevier]

Abstract: In the Maximum Common Edge Subgraph Problem (), given two graphs and with the same number of vertices, one has to find a common subgraph of and (not necessarily induced) with the maximum number of edges. This problem arises in parallel programming environments, and was first defined in Bokhari (1981) [2]. This paper presents a new integer programming formulation for the and a polyhedral study of this model. Several classes of valid inequalities are identified, most of which are shown to define facets. These findings were incorporated into a branch&cut algorithm we implemented. Experimental results with this algorithm are reported. [Copyright &y& Elsevier]

Focuses on a study which proposed an alternative mixed integer linear disjunctive formulation for transmission network expansion. Classical non-linear formulation of the transmission expansion problem; Disjunctive mixed integer formulation of the transmission expansion problem; Standard and alternative disjunctive models.