Almost disjoint spanning trees: relaxing the conditions for completely independent spanning treesReportar como inadecuado




Almost disjoint spanning trees: relaxing the conditions for completely independent spanning trees - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Le2i - Laboratoire Electronique, Informatique et Image 2 LAMSADE - Laboratoire d-analyse et modélisation de systèmes pour l-aide à la décision

Abstract : The search of spanning trees with interesting disjunction properties has led to the introduction of edge-disjoint spanning trees, independent spanning trees and more recently completely independent spanning trees. We group together these notions by defining i, j-disjoint spanning trees, where i j, respectively is the number of vertices edges, respectively that are shared by more than one tree. We illustrate how i, j-disjoint spanning trees provide some nuances between the existence of disjoint connected dominating sets and completely independent spanning trees. We prove that determining if there exist two i, j-disjoint spanning trees in a graph G is NP-complete, for every two positive integers i and j. Moreover we prove that for square of graphs, k-connected interval graphs, complete graphs and several grids, there exist i, j-disjoint spanning trees for interesting values of i and j.





Autor: Benoit Darties - Nicolas Gastineau - Olivier Togni -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados