• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Almost disjoint spanning trees: Relaxing the conditions for completely independent spanning trees

Thumbnail
Date
2018
Link to item file
https://hal.archives-ouvertes.fr/hal-01715892
Dewey
Principes généraux des mathématiques
Sujet
Completely independent spanning trees; Disjoint connected dominating sets; Independent spanning trees; Grid; Spanning trees
Journal issue
Discrete Applied Mathematics
Volume
236
Publication date
2018
Article pages
124-136
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.dam.2017.11.018
URI
https://basepub.dauphine.fr/handle/123456789/21008
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Darties, Benoit
Gastineau, Nicolas
Togni, Olivier
Type
Article accepté pour publication ou publié
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é

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.