Almost disjoint spanning trees: Relaxing the conditions for completely independent spanning trees
Date
2018Link to item file
https://hal.archives-ouvertes.fr/hal-01715892Dewey
Principes généraux des mathématiquesSujet
Completely independent spanning trees; Disjoint connected dominating sets; Independent spanning trees; Grid; Spanning treesJournal issue
Discrete Applied MathematicsVolume
236Publication date
2018Article pages
124-136Publisher
ElsevierCollections
Metadata
Show full item recordAuthor
Darties, Benoit
Gastineau, Nicolas
Togni, Olivier
Type
Abstract (EN)
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 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.Related items
Showing items related by title, author, creator and subject.
-
Connection situations under Uncertainty and Cost Monotonic Solutions
Branzei, Rodica; Gök, Zeynep Alparslan; Moretti, Stefano; Tijs, Stef (2011) Article accepté pour publication ou publié -
Two-stage stochastic matching and spanning tree problems: Polynomial instances and approximation
Gourvès, Laurent; Escoffier, Bruno; Spanjaard, Olivier; Monnot, Jérôme (2010) Article accepté pour publication ou publié -
Approximating minimum spanning tree of depth 2
Alfandari, Laurent; Paschos, Vangelis (1999) Article accepté pour publication ou publié