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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - يونيو 2010

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

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

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


أدرس بدقة موضوعات البحث “On minimum power connectivity problems'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا