A linear time algorithm for finding an Euler walk in a strongly connected 3-uniform hypergraph
Zbigniew Lonc, Paweł Naroski
Abstract
By an Euler walk in a 3-uniform hypergraph H
we mean an alternating sequence
v0,e1,v1,e2,v2,…,vm-1,em,vm
of vertices and edges in H such that each edge of
H appears in this sequence exactly once and
vi-1,vi∈ei,
vi-1¬=vi , for every
i=1,2,…,m. This concept is a natural extension of
the graph theoretic notion of an Euler walk to the case of
3-uniform hypergraphs. We say that a
3-uniform hypergraph H is strongly
connected if it has no isolated vertices and for each two edges
e and f in H there is a
sequence of edges starting with e and ending with
f such that each two consecutive edges in this sequence
have two vertices in common. In this paper we give an algorithm that
constructs an Euler walk in a strongly connected
3-uniform hypergraph (it is known that such a walk in
such a hypergraph always exists). The algorithm runs in time
O(m), where m is the number of edges in the
input hypergraph.
Full Text: PDF PostScript