کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871529 | 1440187 | 2018 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Almost disjoint spanning trees: Relaxing the conditions for completely independent spanning trees
ترجمه فارسی عنوان
تقریبا بی نظیر درختان کاشته شده: آرامش شرایط برای درختان به طور کامل مستقل پوشش داده شده است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
درختان دراز مستقل درختان درختی، مجموعه های غالب وابسته به یکپارچه، درختان مستقل کاملا مستقل، توری،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 236, 19 February 2018, Pages 124-136
Journal: Discrete Applied Mathematics - Volume 236, 19 February 2018, Pages 124-136
نویسندگان
Benoît Darties, Nicolas Gastineau, Olivier Togni,