Contributed Session Thu.1.H 2013

Thursday, 10:30 - 12:00 h, Room: H 2013

Cluster 11: Integer & mixed-integer programming [...]

Polyhedral combinatorics

 

Chair: Vinicius Leal do Forte

 

 

Thursday, 10:30 - 10:55 h, Room: H 2013, Talk 1

Diego Delle Donne
Vertex coloring polytopes over trees and block graphs

Coauthor: Javier L. Marenco

 

Abstract:
Many variants of the vertex coloring problem have been defined, such as precoloring extension, \mu-coloring, ( γ , \mu)-coloring, and list coloring. These problems are NP-hard, as they generalize the classical vertex coloring problem. On the other side, there exist several families of graphs for which some of these problems can be solved in polynomial time. The standard integer programming model for coloring problems uses a binary variable xvc for each vertex v and each color c to indicate whether v is assigned c or not. An extension of this model considers binary variables wc for each color c to indicate whether color c is used or not. In this work we study this formulation for the polynomial cases of the coloring problems mentioned above. In particular, we prove that if the classical vertex coloring problem yields an integer polytope for a family of graphs, then the same holds for \mu-coloring, ( γ , \mu)-coloring, and list coloring over the same family. We prove that the polytope associated to these problems over trees is integer, and we provide empirical evidence suggesting that the same holds for block graphs.

 

 

Thursday, 11:00 - 11:25 h, Room: H 2013, Talk 2

Vinicius Leal do Forte
Formulations and exact solution algorithms for the minimum two-connected dominating set problem

Coauthors: Abilio Lucena, Nelson Maculan

 

Abstract:
Given an undirected graph G=(V,E) a dominating set is a subset D of V such that any vertex of V is in D or has a neighbor vertex in D. The dominating set is 2-connected if the subgraph G(D), it induces in G, is 2-connected and the Minimum 2-Connected Dominating Set Problem (M2CDSP) asks for a least cardinality 2-connected D. The problem has applications in the design of ad-hoc wireless telecommunication networks. However no exact solution algorithm or heuristic appears to exist for it in the literature. In this presentation we discuss a number of different formulations for the M2CDSP as well as some valid inequalities to strengthen them. The formulations address the two variants of the problem, namely the 2-edge connected and the 2-node connected ones and are based on either cut-set inequalities or multi-commodity flows. Preliminary computational results are discussed for branch and cut algorithms based on these formulations.

 

  Online lending company provides a wide range of ways to get money by means of Payday Loans Tennessee. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis was obtained in Europe, Australia, New Zealand.