The Library
Comparing Imperfection Ratio and Imperfection Index for Graph Classes
Tools
Koster, Arie M. C. A. and Wagler, Annegret K. (2008) Comparing Imperfection Ratio and Imperfection Index for Graph Classes. In: 5th ALIO/EURO Workshop on Applied Combinatorial Optimization, Paris, France, Oct 26-28, 2005. Published in: RAIRO - Operations Research, Vol.42 (No.4). pp. 485-500. doi:10.1051/ro:2008030 ISSN 0399-0559.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1051/ro:2008030
Abstract
Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs G where the stable set polytope STAB(G) coincides with the fractional stable set polytope QSTAB(G). For all imperfect graphs G it holds that STAB(G). QSTAB(G). It is, therefore, natural to use the difference between the two polytopes in order to decide how far an imperfect graph is away from being perfect. We discuss three different concepts, involving the facet set of STAB(G), the disjunctive index of QSTAB(G), and the dilation ratio of the two polytopes.
Including only certain types of facets for STAB(G), we obtain graphs that are in some sense close to perfect graphs, for example minimally imperfect graphs, and certain other classes of so-called rank-perfect graphs. The imperfection ratio has been introduced by Gerke and Mc-Diarmid [12] as the dilation ratio of STAB(G) and QSTAB(G), whereas Aguilera et al. [1] suggest to take the disjunctive index of QSTAB(G) as the imperfection index of G. For both invariants there exist no general upper bounds, but there are bounds known for the imperfection ratio of several graph classes [7,12].
Outgoing from a graph-theoretical interpretation of the imperfection index, we prove that there exists no upper bound on the imperfection index for those graph classes with a known bounded imperfection ratio. Comparing the two invariants on those classes, it seems that the imperfection index measures imperfection much more roughly than the imperfection ratio; we, therefore, discuss possible directions for refinements.
Item Type: | Conference Item (UNSPECIFIED) | ||||
---|---|---|---|---|---|
Subjects: | H Social Sciences > HD Industries. Land use. Labor > HD28 Management. Industrial Management | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | RAIRO - Operations Research | ||||
Publisher: | E D P Sciences | ||||
ISSN: | 0399-0559 | ||||
Official Date: | October 2008 | ||||
Dates: |
|
||||
Volume: | Vol.42 | ||||
Number: | No.4 | ||||
Number of Pages: | 16 | ||||
Page Range: | pp. 485-500 | ||||
DOI: | 10.1051/ro:2008030 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Title of Event: | 5th ALIO/EURO Workshop on Applied Combinatorial Optimization | ||||
Type of Event: | Workshop | ||||
Location of Event: | Paris, France | ||||
Date(s) of Event: | Oct 26-28, 2005 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |