Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/13464
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Cohen, David A. | - |
dc.contributor.author | Jeavons, Peter G. | - |
dc.contributor.author | GYSSENS, Marc | - |
dc.date.accessioned | 2012-03-21T15:11:19Z | - |
dc.date.available | 2012-03-21T15:11:19Z | - |
dc.date.issued | 1994 | - |
dc.identifier.citation | Barcelo, Hélène; Kalai, Gil (Ed.). Jerusalem Combinatorics '93, p. 161-177 | - |
dc.identifier.isbn | 978-0-8218-0294-6 (p) and 978-0-8218-7769-2 (e) | - |
dc.identifier.issn | 0271-4132 | - |
dc.identifier.uri | http://hdl.handle.net/1942/13464 | - |
dc.description.abstract | Hypergraphs arise in a variety of applications and are commonly classified as cyclic or acyclic. In this paper we develop a more refined classification scheme for cyclic hypergraphs based on a natural decomposition strategy. The fundamental building blocks in our decompositions are subsets of edges known as k-hinges. For any hypergraph, a set of more than k of its edges is defined to be a k-hinge if all connected components of the hypergraph with respect to the set of edges meet the latter within at most k of its edges. A k-hinge tree is a set of minimal k-hinges that cover all edges of H, and form a tree with respect to intersection. The size of the largest node in any 1-hinge tree is shown to be an invariant of the hypergraph, which we call the degree of cylicity 2. The concept of degree of cyclicity was first presented by Gyssens in the context of relational database design, but is presented here for arbitrary hypergraphs with a greatly simplified proof. For more general k-hinges we show that it is impossible to obtain more powerful decompositions. However, in this case there may be several possible decompositions which do not share any structural invariant. We therefore consider restrictions on k-hinges which are neccesary in order to guarantee this structural invariant. | - |
dc.language.iso | en | - |
dc.publisher | American Mathematical Society | - |
dc.relation.ispartofseries | CONTEMPORARY MATHEMATICS | - |
dc.rights | Copyright 1994 American Mathematical Society | - |
dc.title | A structural decomposition for hypergraphs | - |
dc.type | Proceedings Paper | - |
local.bibliographicCitation.authors | Barcelo, Hélène | - |
local.bibliographicCitation.authors | Kalai, Gil | - |
local.bibliographicCitation.conferencedate | 9-17 May 1993 | - |
local.bibliographicCitation.conferencename | Jerusalem Combinatorics '93 | - |
local.bibliographicCitation.conferenceplace | Jerusalem, Israel | - |
dc.identifier.epage | 177 | - |
dc.identifier.spage | 161 | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
local.relation.ispartofseriesnr | 178 | - |
dc.bibliographicCitation.oldjcat | C2 | - |
dc.identifier.doi | 10.1090/conm/178 | - |
local.bibliographicCitation.btitle | Jerusalem Combinatorics '93 | - |
item.accessRights | Open Access | - |
item.fullcitation | Cohen, David A.; Jeavons, Peter G. & GYSSENS, Marc (1994) A structural decomposition for hypergraphs. In: Barcelo, Hélène; Kalai, Gil (Ed.). Jerusalem Combinatorics '93, p. 161-177. | - |
item.fulltext | With Fulltext | - |
item.contributor | Cohen, David A. | - |
item.contributor | Jeavons, Peter G. | - |
item.contributor | GYSSENS, Marc | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
10.1.1.43.8725[1].pdf | Non peer-reviewed author version | 224.32 kB | Adobe PDF | View/Open |
Page view(s)
86
checked on Sep 6, 2022
Download(s)
158
checked on Sep 6, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.