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.

	PDF Tm-du-8603.pdf Restricted to Repository staff only Download (353kB)
	Indexer Terms (Generate index codes conversion from application/pdf to indexcodes) indexcodes.txt Restricted to Repository staff only Download (4kB)

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:	Monograph (Technical Report)
Uncontrolled Keywords:	Hypergraphs;Strong perfect graph conjecture;Relational databases
Subjects:	MATHEMATICAL AND COMPUTER SCIENCES > Mathematical and Computer Scienes(General)
Depositing User:	Mr. Ravikumar R
Date Deposited:	19 Sep 2006
Last Modified:	24 May 2010 04:20
URI:	http://nal-ir.nal.res.in/id/eprint/2753

Actions (login required)

View Item