The -median polytope of -free graphs: An application of the matching theory

✍ Scribed by Gautier Stauffer

• Publisher: Elsevier Science
• Year: 2008
• Tongue: English
• Weight: 265 KB
• Volume: 36
• Category: Article
• ISSN: 0167-6377
• DOI: 10.1016/j.orl.2007.09.006

✦ Synopsis

Recently, Baiou and Barahona [M. Baiou, F. Barahona, On the p-median polytope of Y -free graphs. Discrete Optimization (in press, available online October 2007)] gave a characterization of the p-median polytope for Y -free graphs. In this paper, we give an alternative proof of this result by reducing the p-median problem in those graphs to a matching problem and then by building upon powerful results from the matching theory.