Generating sparse 2—Spanners

Guy Kortsarz; David Peleg

doi:10.1007/3-540-55706-7_7

Generating sparse 2—Spanners

Guy Kortsarz
, David Peleg

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

ملخص

A k- spanner of a connected graph G=(V, E) is a subgraph G' consisting of all the vertices of V and a subset of the edges, with the additional property that the distance between any two vertices in G' is larger than that distance in G by no more than a factor of k. This note concerns the problem of finding the sparsest 2-spanner in a given graph, and presents an approximation algorithm for this problem with approximation ratio log(|E|/|V|).

اللغة الأصلية	الإنجليزيّة
عنوان منشور المضيف	Algorithm Theory – SWAT 1992 - 3rd Scandinavian Workshop on Algorithm Theory, Proceedings
المحررون	Otto Nurmi, Esko Ukkonen
ناشر	Springer Verlag
الصفحات	73-82
عدد الصفحات	10
رقم المعيار الدولي للكتب (المطبوع)	9783540557067
المعرِّفات الرقمية للأشياء	https://doi.org/10.1007/3-540-55706-7_7
حالة النشر	نُشِر - 1992
منشور خارجيًا	نعم
الحدث	3rd Scandinavian Workshop on Algorithm Theory, SWAT 1992 - Helsinki, فنلندا المدة: ٨ يوليو ١٩٩٢ → ١٠ يوليو ١٩٩٢

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

الاسم	Lecture Notes in Computer Science
مستوى الصوت	621 LNCS
رقم المعيار الدولي للدوريات (المطبوع)	0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)	1611-3349

!!Conference

!!Conference	3rd Scandinavian Workshop on Algorithm Theory, SWAT 1992
الدولة/الإقليم	فنلندا
المدينة	Helsinki
المدة	٨/٠٧/٩٢ → ١٠/٠٧/٩٢

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

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1992.

الوصول إلى المستند

10.1007/3-540-55706-7_7

الملفات والروابط الأخرى

Link to publication in Scopus

قم بذكر هذا

@inproceedings{6d8047f9aaca42ca81093b3349690c0e,

title = "Generating sparse 2—Spanners",

abstract = "A k- spanner of a connected graph G=(V, E) is a subgraph G' consisting of all the vertices of V and a subset of the edges, with the additional property that the distance between any two vertices in G' is larger than that distance in G by no more than a factor of k. This note concerns the problem of finding the sparsest 2-spanner in a given graph, and presents an approximation algorithm for this problem with approximation ratio log(|E|/|V|).",

author = "Guy Kortsarz and David Peleg",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1992.; 3rd Scandinavian Workshop on Algorithm Theory, SWAT 1992 ; Conference date: 08-07-1992 Through 10-07-1992",

year = "1992",

doi = "10.1007/3-540-55706-7\_7",

language = "אנגלית",

isbn = "9783540557067",

series = "Lecture Notes in Computer Science",

publisher = "Springer Verlag",

pages = "73--82",

editor = "Otto Nurmi and Esko Ukkonen",

booktitle = "Algorithm Theory – SWAT 1992 - 3rd Scandinavian Workshop on Algorithm Theory, Proceedings",

address = "גרמניה",

}

Kortsarz, G & Peleg, D 1992, Generating sparse 2—Spanners. في O Nurmi & E Ukkonen (المحررون), Algorithm Theory – SWAT 1992 - 3rd Scandinavian Workshop on Algorithm Theory, Proceedings. Lecture Notes in Computer Science, المجلد 621 LNCS, Springer Verlag, الصفحات 73-82, 3rd Scandinavian Workshop on Algorithm Theory, SWAT 1992, Helsinki, فنلندا, ٨/٠٧/٩٢. https://doi.org/10.1007/3-540-55706-7_7

Generating sparse 2—Spanners. / Kortsarz, Guy; Peleg, David.
Algorithm Theory – SWAT 1992 - 3rd Scandinavian Workshop on Algorithm Theory, Proceedings. محرر / Otto Nurmi; Esko Ukkonen. Springer Verlag, 1992. صفحة 73-82 (Lecture Notes in Computer Science; المجلد 621 LNCS).

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

TY - GEN

T1 - Generating sparse 2—Spanners

AU - Kortsarz, Guy

AU - Peleg, David

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1992.

PY - 1992

Y1 - 1992

N2 - A k- spanner of a connected graph G=(V, E) is a subgraph G' consisting of all the vertices of V and a subset of the edges, with the additional property that the distance between any two vertices in G' is larger than that distance in G by no more than a factor of k. This note concerns the problem of finding the sparsest 2-spanner in a given graph, and presents an approximation algorithm for this problem with approximation ratio log(|E|/|V|).

AB - A k- spanner of a connected graph G=(V, E) is a subgraph G' consisting of all the vertices of V and a subset of the edges, with the additional property that the distance between any two vertices in G' is larger than that distance in G by no more than a factor of k. This note concerns the problem of finding the sparsest 2-spanner in a given graph, and presents an approximation algorithm for this problem with approximation ratio log(|E|/|V|).

UR - https://www.scopus.com/pages/publications/85030534935

U2 - 10.1007/3-540-55706-7_7

DO - 10.1007/3-540-55706-7_7

M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???

AN - SCOPUS:85030534935

SN - 9783540557067

T3 - Lecture Notes in Computer Science

SP - 73

EP - 82

BT - Algorithm Theory – SWAT 1992 - 3rd Scandinavian Workshop on Algorithm Theory, Proceedings

A2 - Nurmi, Otto

A2 - Ukkonen, Esko

PB - Springer Verlag

T2 - 3rd Scandinavian Workshop on Algorithm Theory, SWAT 1992

Y2 - 8 July 1992 through 10 July 1992

ER -

Generating sparse 2—Spanners

ملخص

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

!!Conference

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

الوصول إلى المستند

الملفات والروابط الأخرى

بصمة

قم بذكر هذا