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

!!Conference15th 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.

بصمة

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

قم بذكر هذا