Mostrar el registro sencillo del ítem

Computing the clique number of a-perfect graphs in polynomial time

hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorPÊCHER, Arnaud
hal.structure.identifierLaboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes [LIMOS]
dc.contributor.authorWAGLER, Annegret K.
dc.date.accessioned2024-04-04T02:20:38Z
dc.date.available2024-04-04T02:20:38Z
dc.date.issued2014
dc.identifier.issn0195-6698
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/189508
dc.description.abstractEnA 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.isoen
dc.publisherElsevier
dc.title.enComputing the clique number of a-perfect graphs in polynomial time
dc.typeArticle de revue
dc.identifier.doi10.1016/j.ejc.2013.06.025
dc.subject.halSciences de l'Homme et Société/Sciences de l'information et de la communication
bordeaux.journalEuropean Journal of Combinatorics
bordeaux.page449-458
bordeaux.volume35
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-00920846
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00920846v1
bordeaux.COinSctx_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


Archivos en el ítem

ArchivosTamañoFormatoVer

No hay archivos asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem