On Rooted k-Connectivity Problems in Quasi-bipartite Digraphs

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


We consider the directed Rooted Subset k -Edge-Connectivity problem: given a digraph G= (V, E) with edge costs, a set T⊂ V of terminals, a root node r, and an integer k, find a min-cost subgraph of G that contains k edge disjoint rt-paths for all t∈ T. The case when every edge of positive cost has head in T admits a polynomial time algorithm due to Frank [9], and the case when all positive cost edges are incident to r is equivalent to the k -Multicover problem. Recently, Chan et al. [2] obtained ratio O(ln kln | T| ) for quasi-bipartite instances, when every edge in G has an end (tail and/or head) in T+ r. We give a simple proof for the same ratio for a more general problem of covering an arbitrary T-intersecting supermodular set function by a minimum cost edge set, and for the case when only every positive cost edge has an end in T+ r.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفComputer Science – Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Proceedings
المحررونRahul Santhanam, Daniil Musatov
ناشرSpringer Science and Business Media Deutschland GmbH
عدد الصفحات10
رقم المعيار الدولي للكتب (المطبوع)9783030794156
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2021
الحدث16th International Computer Science Symposium in Russia, CSR 2021 - Sochi, روسيا
المدة: ٢٨ يونيو ٢٠٢١٢ يوليو ٢٠٢١

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

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


!!Conference16th International Computer Science Symposium in Russia, CSR 2021

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

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.


أدرس بدقة موضوعات البحث “On Rooted k-Connectivity Problems in Quasi-bipartite Digraphs'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا