On minimum power connectivity problems

Yuval Lando, Zeev Nutov

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

תקציר

Given a (directed or undirected) graph with edge costs, the power of a node is the maximum cost of an edge leaving it, and the power of the graph is the sum of the powers of its nodes. Motivated by applications for wireless networks, we present polynomial and improved approximation algorithms, as well as inapproximability results, for some classic network design problems under the power minimization criteria. Our main result is for the problem of finding a min-power subgraph that contains k internally-disjoint vs-paths from every node v to a given node s: we give a polynomial algorithm for directed graphs and a logarithmic approximation algorithm for undirected graphs. In contrast, we will show that the corresponding edge-connectivity problems are unlikely to admit even a polylogarithmic approximation.

שפה מקוריתאנגלית
עמודים (מ-עד)164-173
מספר עמודים10
כתב עתJournal of Discrete Algorithms
כרך8
מספר גיליון2
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - יוני 2010

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

Copyright:
Copyright 2010 Elsevier B.V., All rights reserved.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'On minimum power connectivity problems'. יחד הם יוצרים טביעת אצבע ייחודית.

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