Decomposition of a hypergraph by partial-edge separators

✍ Scribed by Francesco Mario Malvestuto; Marina Moscarini

• Book ID: 104326525
• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 223 KB
• Volume: 237
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(98)00128-5

✦ Synopsis

The notion of vertex separability by partial edges for a simple hypergraph is introduced and the related structural properties of the hypergraph are analyzed in terms of maximal (with respect to set-theoretic inclusion) compacts and of dividers, where a compact is a vertex set in which every two vertices are separated by no partial edge, and a divider is a partial edge X for which there exists a pair of vertices that are separated by X and by no proper subset of X . It is proven that, given a hypergraph H , the hypergraph (called the compaction of H ) made up of maximal compacts of H is acyclic and coincides with H if and only if H is acyclic; furthermore, it has the same dividers as H , and can be characterized as being the unique acyclic hypergraph that has the same compacts as H . Polynomial algorithms for ÿnding maximal compacts and dividers of a given hypergraph are provided. Finally, an application to the problem of computing the maximum-entropy extension of a system of marginals over a hypergraph is discussed.