Tropical Graph Parameters

Résumé : Les matrices de connexion pour des fonctions sur les graphes à valeurs dans un corps ont été introduites par M. Freedman, L. Lovász and A. Schrijver (2007). Une fonctions sur les graphes ayant des matrices de connexion de rang fini peut être calculée en temps polynomial sur toute famille de graphes de largeur arborescente (”tree-width”) bornée. Nous introduisons des matrices de jointure (”join matrices”) qui généralisent les matrices de connexion, et nous permettons aux fonctions sur les graphes de prendre leurs valeurs dans des semianneaux tropicaux réels. Nous montrons qu’une fonction sur les graphes ayant des matrices de jointure de rang fini peut être calculée en temps polynomial sur des graphes de largeur de clique (”clique-width”) bornée. Dans le cas des semi-anneaux commutatifs, cela reste vrai pour les graphes de largeur de clique linéaire bornée. B. Godlin, T. Kotek and J.A. Makowsky (2008) ont montré que certaines hypothèses de definissabilité en Logique du Second Ordre Monadique concernant des opérations sur les graphes entraine la finitude des rangs. Nous exhibons un ensemble non dénombrable d’opérations ayant une matrice de connexion et des matrices de jointure de rang fini. Cela démontre que l’hypothèse de rang fini est beaucoup plus faible que l’hypothèse de definissabilité.
Type de document :
Communication dans un congrès
Louis J. Billera and Isabella Novik. 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), 2014, Chicago, United States. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), pp.357-368, 2014, DMTCS Proceedings
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01207605
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 1 octobre 2015 - 09:29:09
Dernière modification le : dimanche 31 décembre 2017 - 09:44:02
Document(s) archivé(s) le : samedi 2 janvier 2016 - 10:54:39

Fichier

dmAT0132.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01207605, version 1

Collections

Citation

Nadia Labai, Johann Makowsky. Tropical Graph Parameters. Louis J. Billera and Isabella Novik. 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), 2014, Chicago, United States. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), pp.357-368, 2014, DMTCS Proceedings. 〈hal-01207605〉

Partager

Métriques

Consultations de la notice

101

Téléchargements de fichiers

264