Tutte seminar - Yuri FaenzaExport this event to calendar

Friday, May 21, 2010 — 3:30 PM to 4:30 PM EDT

The matching structure behind the composition of strips

Speaker: Yuri Faenza
Affiliation: Università di Roma "Tor Vergata"
Room: Mathematics & Computer Building (MC) 5158

Abstract:

A strip is a triple (G,a,b), where G is a simple, undirected graph and a,b are vertices of G whose neighborhood is a clique. The composition of strips takes as input a set of strips, and outputs a graph. Chudnovsky and Seymour showed that strips from a suitable family form the building blocks of a wide class of claw-free graphs, meaning that every graph in this class can be expressed as the composition of strips from the family, and conversely a composition of those strips always produces a claw-free graph from this class. One of the reasons why claw-free graphs attracted the interest of many researchers is that they generalize line graphs, thus the Maximum (Weighted) Stable Set problem on claw-free graphs generalizes the maximum (weighted) matching problem. 

In this talk we show that, in fact, MWSS problems on graphs that are the composition of strips share a common matching-like structure, both from an algorithmic and from a polyhedral point of view. We also address a number of applications of these results, mainly back in the context of claw-free graphs, including extended formulations and a polytime separation routine for the stable set polytope of claw-free graphs, and a new combinatorial algorithm for the MWSS on claw-free graphs. These latter results use a novel algorithmic decomposition theorem for claw-free graphs with stability number at least 4. 

These results are part of the speaker's PhD thesis, and are a joint work with G.Oriolo and G. Stauffer.

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
  1. 2020 (8)
    1. January (8)
  2. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  3. 2018 (138)
  4. 2017 (103)
  5. 2016 (137)
  6. 2015 (136)
  7. 2014 (88)
  8. 2013 (48)
  9. 2012 (39)
  10. 2011 (36)
  11. 2010 (40)
  12. 2009 (40)
  13. 2008 (39)
  14. 2007 (15)