ملخص
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 |
المعرِّفات الرقمية للأشياء | |
حالة النشر | نُشِر - 2007 |
الحدث | 15th Annual European Symposium on Algorithms, ESA 2007 - Eilat, إسرائيل المدة: ٨ أكتوبر ٢٠٠٧ → ١٠ أكتوبر ٢٠٠٧ |
سلسلة المنشورات
الاسم | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
مستوى الصوت | 4698 LNCS |
رقم المعيار الدولي للدوريات (المطبوع) | 0302-9743 |
رقم المعيار الدولي للدوريات (الإلكتروني) | 1611-3349 |
!!Conference
!!Conference | 15th Annual European Symposium on Algorithms, ESA 2007 |
---|---|
الدولة/الإقليم | إسرائيل |
المدينة | Eilat |
المدة | ٨/١٠/٠٧ → ١٠/١٠/٠٧ |
ملاحظة ببليوغرافية
Funding Information:This research was supported by The Open University of Israel's Research Fund, grant no. 46102.