




















An Euler tour in a hypergraph is a closed walk that traverses each edge of the hypergraph exactly once, while an Euler family is a family of closed walks that jointly traverse each edge exactly once and cannot be concatenated. In this paper, we show how the problem of existence of an Euler tour (family) in a hypergraph $H$ can be reduced to the analogous problem in some smaller hypergraphs that are derived from $H$ using an edge cut of $H$. In the process, new techniques of edge cut assignments and collapsed hypergraphs are introduced. Moreover, we describe algorithms based on these characterizations that determine whether or not a hypergraph admits an Euler tour (family), and can also construct an Euler tour (family) if it exists.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。