Retour

Séance MB5 - Invariants graphiques / Graph Invariants

Jour lundi, le 7 mai 2007
Salle Dutailier International
Président Odile Marcotte

Présentations

15h30-
15h55
New Upper and Lower Bounds for the Maximum Clique Problem
  Alain Hertz, GERAD et École Polytechnique de Montréal, Mathématiques et génie industriel, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7
Bernard Gendron, Université de Montréal, CRT
Patrick St-Louis, Université de Montréal, Informatique et recherche opérationnelle, C.P. 6128, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3J7

We consider the problem of determining the size w(G) of a maximum clique in a graph G. Given any procedure U that computes an upper bound U(G) on w(G), we present a decomposition algorithm that produces an upper bound U’(G) that is at least as good as U(G). Tests on DIMACS instances demonstrate that the proposed algorithm is able, in average, to reduce the gap between U(G) and w(G) by about 60%. We also show how to use our algorithm to improve the computation of lower bounds on w(G).


15h55-
16h20
Average Distance and Maximum Induced Forest
  David Schindl, GERAD et École Polytechnique de Montréal, Montréal, Québec, Canada, H3T 2A7
Pierre Hansen, GERAD et HEC Montréal, Méthodes quantitatives de gestion, 3000, chemin de la Côte-Sainte-Catherine, Montréal, Québec, Canada, H3T 2A7
Alain Hertz, GERAD et École Polytechnique de Montréal, Mathématiques et génie industriel, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7
Rim Kilani, GERAD et École Polytechnique de Montréal, Mathématiques et génie industriel, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7
Odile Marcotte, GERAD et Université du Québec à Montréal, Informatique, C.P. 8888, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3P8

We prove that the average distance between the vertices of a connected graph does not exceed half the maximum size (number of vertices) of an induced forest (graph without cycles). As a corollary, this result permits to give a positive answer to a 15 years old conjecture. We also announce a stronger conjecture.


16h20-
16h45
Automated Results and Conjectures about the Randic Index.
  Mustapha Aouchiche, GERAD et HEC Montréal, Montréal, Québec, Canada, H3C 3A7
Pierre Hansen, GERAD et HEC Montréal, Méthodes quantitatives de gestion, 3000, chemin de la Côte-Sainte-Catherine, Montréal, Québec, Canada, H3T 2A7
Maolin Zheng, Fair Isaac Corporation, San Diego, California, USA

The Randic index, a graph invariant with applications in chemistry, is widely studied by graph theorists. Since its definition by Randic in 1975, more than 1500 papers deal with it. Using the AutoGraphiX system, an automated comparison, of the Randic index with some of the most studied invariants in graph theory, is made. Here, we report on the results and conjectures involving 9 invariants: minimum, average and maximum degree, diameter, girth, algebraic and node connectivity, index and matching numbers.


16h45-
17h10
On the 2-Stability Number
  Rim Kilani, GERAD et École Polytechnique de Montréal, Mathématiques et génie industriel, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7
Pierre Hansen, GERAD et HEC Montréal, Méthodes quantitatives de gestion, 3000, chemin de la Côte-Sainte-Catherine, Montréal, Québec, Canada, H3T 2A7
Alain Hertz, GERAD et École Polytechnique de Montréal, Mathématiques et génie industriel, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7
Odile Marcotte, GERAD et Université du Québec à Montréal, Informatique, C.P. 8888, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3P8
David Schindl, GERAD et École Polytechnique de Montréal, Montréal, Québec, Canada, H3T 2A7

The 2-stability number of a graph G is the largest number of vertices in a 2-colorable subgraph of G. A graph is 2-stable-critical if it has no isolated vertices and removing any of its edges increases its 2-stability number. We study 2-stable-critical graphs using the AutoGraphiX system.


Retour