TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1993

COGA 5-Wheel

Page Content

to Navigation

Preprints 1993

Modeling Hypergraphs by Graphs
Citation key Report-343-1992
Author Edmund Ihler and Dorothea Wagner and Frank Wagner
Pages 171-175
Year 1992
Journal Information Processing Letters, 1993
Volume 45
Number 343
Institution Technische Universität Berlin, Institut für Mathematik
Abstract An elegant and general way to apply graph partitioning algorithms to hypergraphs would be to model hypergraphs by graphs and apply the graph algorithms to these models. Of course such models have to simulate the given hypergraphs with respect to their cut properties. An edge-weighted graph $(V,E)$ is a cut-model\/ for an edge-weighted hypergraph $(V,H)$ if the weight of the edges cut by any bipartition of $V$ in the graph is the same as the weight of the hyperedges cut by the same bipartition in the hypergraph. We show that there is no cut-model in general. Next we examine whether the addition of dummy vertices helps: An edge-weighted graph $(V\cup D,E)$ is a mincut-model\/ for an edge-weighted hypergraph $(V,H)$ if the weight of the hyperedges cut by a bipartition of the hypergraphs vertices is the same as the weight of a minimum cut separating the two parts in the graph. We construct such models using positive and\/ negative weights. On the other hand, we show that there is no mincut-model in general if only positive weights are allowed.
Bibtex Type of Publication Preprint
Download Bibtex entry

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe