Degree-constrained node-connectivity

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

We give a general framework to handle node-connectivity degree constrained problems. In particular, for the κ-Outconnected Subgraph problem, for both directed and undirected graphs, our algorithm computes in polynomial time a solution J of cost O(log κ) times the optimal, such that deg J (v) = O(2 κ ) • b(v) for all ν ∈ V. Similar result are obtained for the Element-Connectivity and the κ-Connected Subgraph problems. The latter is a significant improvement on the particular case of only degree-approximation and undirected graphs considered in [5]. In addition, for the edge-connectivity directed Degree-Constrained κ-Outconnected Subgraph problem, we slightly improve the best known approximation ratio, by a simple proof.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفLATIN 2012
العنوان الفرعي لمنشور المضيفTheoretical Informatics - 10th Latin American Symposium, Proceedings
الصفحات582-593
عدد الصفحات12
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2012
الحدث10th Latin American Symposiumon Theoretical Informatics, LATIN 2012 - Arequipa, البيرو
المدة: ١٦ أبريل ٢٠١٢٢٠ أبريل ٢٠١٢

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت7256 LNCS
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349

!!Conference

!!Conference10th Latin American Symposiumon Theoretical Informatics, LATIN 2012
الدولة/الإقليمالبيرو
المدينةArequipa
المدة١٦/٠٤/١٢٢٠/٠٤/١٢

بصمة

أدرس بدقة موضوعات البحث “Degree-constrained node-connectivity'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا