Bounded Degree Group Steiner Tree Problems

Guy Kortsarz, Zeev Nutov

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء


Motivated by some open problems posed in [13], we study three problems that seek a low degree subtree T of a graph G =(V, E). In the Min-Degree Group Steiner Tree problem we are given a collection of node subsets (groups), and T should contain a node from every group. In the Min-Degree Steiner k-Tree problem we are given a set R of terminals and an integer k, and T should contain k terminals. In both problems the goal is to minimize the maximum degree of T . In the more general Degrees Bounded Min-Cost Group Steiner Tree problem, we are also given edge costs and individual degree bounds (Formula Presented). The output tree T should obey the degree constraints degT (v) ≤ bv for all (Formula Presented), and among all such trees we seek one of minimum cost. When the input is a tree, an O(log2 n) approximation for the cost is given in [10]. Our first result generalizes [10] – we give a bicriteria (O(log2 n), O(log2 n))-approximation algorithm for Degrees Bounded Min-Cost Group Steiner Tree problem on tree inputs. This matches the cost ratio of [10] but also approximates the degrees within O(log2 n). Our second result shows that if Min-Degree Group Steiner Tree admits ratio ρ then Min-Degree Steiner k-Tree admits ratio ρ · O(log k). Combined with [12], this implies an O(log3 n)-approximation for Min-Degree Steiner k-Tree on general graphs, in quasi-polynomial time. Our third result is a polynomial time O(log3 n)-approximation algorithm for Min-Degree Group Steiner Tree on bounded treewidth graphs.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفCombinatorial Algorithms - 31st International Workshop, IWOCA 2020, Proceedings
المحررونLeszek Gasieniec, Leszek Gasieniec, Ralf Klasing, Tomasz Radzik
عدد الصفحات12
رقم المعيار الدولي للكتب (المطبوع)9783030489656
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2020
الحدث31st International Workshop on Combinatorial Algorithms, IWOCA 2020 - Bordeaux, فرنسا
المدة: ٨ يونيو ٢٠٢٠١٠ يونيو ٢٠٢٠

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت12126 LNCS
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349


!!Conference31st International Workshop on Combinatorial Algorithms, IWOCA 2020

ملاحظة ببليوغرافية

Publisher Copyright:
© Springer Nature Switzerland AG 2020.


أدرس بدقة موضوعات البحث “Bounded Degree Group Steiner Tree Problems'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا