Search

Your search keyword '"Faenza Y."' showing total 4 results
Start Over Author "Faenza Y."
4 results on '"Faenza Y."'

1. The total matching polytope of complete bipartite graphs

Author

Faenza, Y, Ferrarini, L, Faenza Y., Ferrarini L., Faenza, Y, Ferrarini, L, Faenza Y., and Ferrarini L.

Abstract

The total matching polytope generalizes the stable set polytope and the matching polytope. In this paper, we first propose new facet-defining inequalities for the total matching polytope. We then give an exponential-sized, non-redundant description in the original space and a compact description in an extended space of the total matching polytope of complete bipartite graphs.

Published
2024

2. Separating stable sets in claw-free graphs via Padberg-Rao and compact linear programs

Author

Faenza, Y., Oriolo, G., Stauffer, G., Stauffer, Gautier, Dipartimento di Ingegneria dell'Impresa [Roma], Università degli Studi di Roma Tor Vergata [Roma], Reformulations based algorithms for Combinatorial Optimization (Realopt), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, and Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)

Subjects
021103 operations research, 0211 other engineering and technologies, 010103 numerical & computational mathematics, 02 engineering and technology, 0101 mathematics, Settore MAT/09 - Ricerca Operativa, 01 natural sciences, ComputingMilieux_MISCELLANEOUS
Abstract

In this paper, we provide the first linear programming formulations for the stable set problem in claw-free graphs, together with polynomial time separation routines for those formulations (they are not compact). We then exploit one of those extended formulations and propose a new polytime algorithm for solving the separation problem for the stable set polytope of claw-free graphs. This routine combines a separation algorithm for the matching polytope due to Padberg and Rao and the solution of (moderate size) compact linear programs. Hence, it does not rely on the ellipsoid method and seems to be appropriate to be inserted in branch and cut frameworks for solving real world problems.

Published
2012

3. Stable Sets in Claw- Free Graphs: A Journey Through Algorithms and Polytopes

Author

Faenza, Y., Oriolo, G., Stauffer, G., and Ventura, P.

Abstract

The problem of finding a maximum weighted stable set in a claw-free graph is a fundamental generalization of the matching problem. It has been therefore investigated by several researchers, and its theory has been developing for more than 40 years. The last 10 years have been particularly productive, mainly due to new approaches that exploit results from structural graph theory. The purpose of this chapter is to help the interested researchers to navigate through the various results in this field and in particular to shed light on the latest achievements and the current open questions.

Published
2011

Catalog

Books, media, physical & digital resources
See catalog results