Large-girth roots of graphs

Abstract : We study the problem of recognizing graph powers and computing roots of graphs. We provide a polynomial time recognition algorithm for r-th powers of graphs of girth at least 2r+3, thus improving a bound conjectured by Farzad et al. (STACS 2009). Our algorithm also finds all r-th roots of a given graph that have girth at least 2r+3 and no degree one vertices, which is a step towards a recent conjecture of Levenshtein that such root should be unique. On the negative side, we prove that recognition becomes an NP-complete problem when the bound on girth is about twice smaller. Similar results have so far only been attempted for r=2,3.
Type de document :
Communication dans un congrès
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.35-46, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00454554
Contributeur : Publications Loria <>
Soumis le : lundi 8 février 2010 - 17:29:45
Dernière modification le : mercredi 29 novembre 2017 - 10:26:30
Document(s) archivé(s) le : vendredi 18 juin 2010 - 19:36:30

Fichier

adamaszek.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00454554, version 1

Collections

Citation

Anna Adamaszek, Michal Adamaszek. Large-girth roots of graphs. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.35-46, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00454554〉

Partager

Métriques

Consultations de la notice

134

Téléchargements de fichiers

126