On Rooted k-Connectivity Problems in Quasi-Bipartite Digraphs

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


We consider the directed Min-Cost Rooted Subset k -Edge-Connection 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 (Discret Appl Math 157(6):1242–1254, 2009), and the case when all positive cost edges are incident to r is equivalent to the k -Multicover problem. Chan et al. (APPROX/RANDOM, 2020) gave an LP-based O(ln kln | T|) -approximation algorithm for quasi-bipartite instances, when every edge in G has at least one end in T∪ { r} . We give a simple combinatorial algorithm with the same approximation ratio for a more general problem of covering an arbitrary T-intersecting supermodular set function by a min-cost edge set, and for the case when only every positive cost edge has at least one end in T∪ { r} .

שפה מקוריתאנגלית
מספר המאמר1
עמודים (מ-עד)10
מספר עמודים1
כתב עתOperations Research Forum
מספר גיליון1
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - מרץ 2024

הערה ביבליוגרפית

Publisher Copyright:
© 2024, The Author(s), under exclusive licence to Springer Nature Switzerland AG.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'On Rooted k-Connectivity Problems in Quasi-Bipartite Digraphs'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי