Bhogle, Srinivas (1986) Classes of hypergraphs, the strong perfect graph conjecture and relational databases. Technical Report. National Aeronautical Laboratory, Bangalore, India.
Full text available as:![[img]](http://nal-ir.nal.res.in/style/images/fileicons/application_pdf.png) | PDF Restricted to Archive staff only Download (344Kb) |
Abstract
Several classes of hypergraphs have been defined, or characterised, in terms of cycles. Such a formulation can be very attractive. For example, to verify that a given13; class of graphs satisfies the Strong Perfect Graph13; Conjecture, one is really required to verify a certain13; condition involving cycles. A formulation using hypergraphs13; can sometimes make this much simpler instead of considering cycles of a 'given graph, G, one looks at cycles of the quot;Helly hypergraphquot; H of G (L(H)=G). We discuss examples where the hypergraphic formulation appears to be superior, and also use this formulation13; to discover new classes of graphs verifying the Strong13; Conjecture.13; 13; Research workers in relational databases, which can be viewed as hypergraphs, are presently studying various13; definitions of acyclicity. It turns out that acyclic13; databases correspond to the well -characterised subtree13; hypergraphs. So can we meaningfully interpret other known classes of hypergraphs in the context of relational13; databases?
| Item Type: | Proj.Doc/Technical Report (Technical Report) |
|---|---|
| Uncontrolled Keywords: | Hypergraphs;Strong perfect graph conjecture;Relational databases |
| Subjects: | MATHEMATICAL AND COMPUTER SCIENCES > Mathematical and Computer Scienes(General) |
| Division/Department: | Information Management Division |
| Depositing User: | Mr. Ravikumar R |
| Date Deposited: | 19 Sep 2006 |
| Last Modified: | 24 May 2010 09:50 |
| URI: | http://nal-ir.nal.res.in/id/eprint/2753 |
Actions (login required)
| View Item |
