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.

 

  Most online loan lenders allow getting New Jersey Loans Online without visiting a bank, straight to your bank account. Therefore, we can say that the active substances in its composition are more perfectly mixed. Vardenafil is not only present in the original Buy Levitra, but also as part of its analogs.