A linear time algorithm for finding an Euler walk in a strongly connected 3-uniform hypergraph

Abstract : By an Euler walk in a 3-uniform hypergraph H we mean an alternating sequence v(0), epsilon(1), v(1), epsilon(2), v(2), ... , v(m-1), epsilon(m), v(m) of vertices and edges in H such that each edge of H appears in this sequence exactly once and v(i-1); v(i) is an element of epsilon(i), v(i-1) not equal v(i), 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2012, Vol. 14 no. 1 (1), pp.147-158
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990565
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 16:19:36
Dernière modification le : jeudi 7 septembre 2017 - 01:03:40
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:37:06

Fichier

2037-6970-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990565, version 1

Collections

Citation

Zbigniew Lonc, Pawel Naroski. A linear time algorithm for finding an Euler walk in a strongly connected 3-uniform hypergraph. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2012, Vol. 14 no. 1 (1), pp.147-158. 〈hal-00990565〉

Partager

Métriques

Consultations de la notice

94

Téléchargements de fichiers

280