On minimum power connectivity problems

Yuval Lando, Zeev Nutov

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

Given a (directed or undirected) graph with costs on the edges, 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 improved approximation algorithms and inapproximability results for some classic network design problems under the power minimization criteria. In particular, we give a logarithmic approximation algorithm for the problem of finding a rninpower subgraph that contains k internally-disjoint paths from a given node s to every other node, and show that several other problems are unlikely to admit a polylogarithmic approximation.

שפה מקוריתאנגלית
כותר פרסום המארחAlgorithms - ESA 2007 - 15th Annual European Symposium, Proceedings
מוציא לאורSpringer Verlag
עמודים87-98
מספר עמודים12
מסת"ב (מודפס)9783540755197
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2007
אירוע15th Annual European Symposium on Algorithms, ESA 2007 - Eilat, ישראל
משך הזמן: 8 אוק׳ 200710 אוק׳ 2007

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך4698 LNCS
ISSN (מודפס)0302-9743
ISSN (אלקטרוני)1611-3349

כנס

כנס15th Annual European Symposium on Algorithms, ESA 2007
מדינה/אזורישראל
עירEilat
תקופה8/10/0710/10/07

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

Funding Information:
This research was supported by The Open University of Israel's Research Fund, grant no. 46102.

טביעת אצבע

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

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