Computing the clique number of a-perfect graphs in polynomial time
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| dc.contributor.author | PÊCHER, Arnaud | |
| hal.structure.identifier | Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes [LIMOS] | |
| dc.contributor.author | WAGLER, Annegret K. | |
| dc.date.accessioned | 2024-04-04T02:20:38Z | |
| dc.date.available | 2024-04-04T02:20:38Z | |
| dc.date.issued | 2014 | |
| dc.identifier.issn | 0195-6698 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/189508 | |
| dc.description.abstractEn | A main result of combinatorial optimization is that the clique and chromatic numbers of a perfect graph are computable in polynomial time (Grotschel et al., 1981) [7]. This result relies on polyhedral characterizations of perfect graphs involving the stable set polytope of the graph, a linear relaxation defined by clique constraints, and a semi-definite relaxation, the Theta-body of the graph.A natural question is whether the algorithmic results for perfect graphs can be extended to graph classes with similar polyhedral properties. We consider a superclass of perfect graphs, the a-perfect graphs, whose stable set polytope is given by constraints associated with generalized cliques. We show that for such graphs the clique number can be computed in polynomial time as well. The result strongly relies upon Fulkerson's antiblocking theory for polyhedra and Lovasz's Theta function. | |
| dc.language.iso | en | |
| dc.publisher | Elsevier | |
| dc.title.en | Computing the clique number of a-perfect graphs in polynomial time | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1016/j.ejc.2013.06.025 | |
| dc.subject.hal | Sciences de l'Homme et Société/Sciences de l'information et de la communication | |
| bordeaux.journal | European Journal of Combinatorics | |
| bordeaux.page | 449-458 | |
| bordeaux.volume | 35 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00920846 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00920846v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=European%20Journal%20of%20Combinatorics&rft.date=2014&rft.volume=35&rft.spage=449-458&rft.epage=449-458&rft.eissn=0195-6698&rft.issn=0195-6698&rft.au=P%C3%8ACHER,%20Arnaud&WAGLER,%20Annegret%20K.&rft.genre=article |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||