Classes of hypergraphs, the strong perfect graph conjecture and relational databases

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] 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