Listing minimal edge-covers of intersecting families with applications to connectivity problems

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

תקציר

Let G = (V, E) be a directed/undirected graph, let s, t ∈ V, and let F be an intersecting family on V (that is, X ∩ Y, X ∪ Y ∈ F for any intersecting X, Y ∈ F) so that s ∈ X and t ∉ X for every X ∈ F. An edge set I ⊆ E is an edge-cover of F if for every X ∈ F there is an edge in I from X to V - X. We show that minimal edge-covers of F can be listed with polynomial delay, provided that, for any I ⊆ E the minimal member of the residual family FI of the sets in F not covered by I can be computed in polynomial time. As an application, we show that minimal undirected Steiner networks, and minimal k-connected and k-outconnected spanning subgraphs of a given directed/undirected graph, can be listed in incremental polynomial time.

שפה מקוריתאנגלית
עמודים (מ-עד)112-117
מספר עמודים6
כתב עתDiscrete Applied Mathematics
כרך157
מספר גיליון1
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 6 ינו׳ 2009

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Listing minimal edge-covers of intersecting families with applications to connectivity problems'. יחד הם יוצרים טביעת אצבע ייחודית.

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