Accession Number : ADA137611
Title : Compositions for Perfect Graphs.
Descriptive Note : Management science research rept.,
Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Personal Author(s) : Cornuejols,G ; Cunningham,W H
PDF Url : ADA137611
Report Date : Oct 1983
Pagination or Media Count : 18
Abstract : It is not known whether perfect graphs can be recognized in polynomial time. One attempt is to use some graph decomposition to decompose a given graph into irreducible components, i.e., components which cannot be decomposed. Perfect graphs can be recognized in polynomial time if: (1) the composition (reverse operation of the decomposition) preserves perfection; (2) reducible graphs can be decomposed in polynomial time into two smaller graphs one of which is irreducible, and (3) irreducible perfect graphs can be recognized in polynomial time. In this paper we introduce a new composition of graphs for which (1) and (2) hold. This composition generalizes clique identification, the join and the amalgam operations and, together with complementation, it encompasses all the operations preserving perfection known to us.
Descriptors : *Graphs, *Decomposition, Numerical methods and procedures, Algorithms, Computations
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE