The dense k-subgraph problem

U. Feige; G. Kortsarz; D. Peleg

doi:10.1007/s004530010050

The dense k-subgraph problem

U. Feige, G. Kortsarz, D. Peleg

מדעי המחשב

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

ملخص

This paper considers the problem of computing the dense k-vertex subgraph of a given graph, namely, the subgraph with the most edges. An approximation algorithm is developed for the problem, with approximation ratio O(n^δ), for some δ < 1/3.

اللغة الأصلية	الإنجليزيّة
الصفحات (من إلى)	410-421
عدد الصفحات	12
دورية	Algorithmica
مستوى الصوت	29
رقم الإصدار	3
المعرِّفات الرقمية للأشياء	https://doi.org/10.1007/s004530010050
حالة النشر	نُشِر - مارس 2001

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

10.1007/s004530010050

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

Link to publication in Scopus

قم بذكر هذا

@article{d4c719f783d64f74ae5c19c7bb2303ce,

title = "The dense k-subgraph problem",

abstract = "This paper considers the problem of computing the dense k-vertex subgraph of a given graph, namely, the subgraph with the most edges. An approximation algorithm is developed for the problem, with approximation ratio O(nδ), for some δ < 1/3.",

keywords = "Approximation algorithms, Dense subgraph",

author = "U. Feige and G. Kortsarz and D. Peleg",

year = "2001",

month = mar,

doi = "10.1007/s004530010050",

language = "אנגלית",

volume = "29",

pages = "410--421",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "3",

}

TY - JOUR

T1 - The dense k-subgraph problem

AU - Feige, U.

AU - Kortsarz, G.

AU - Peleg, D.

PY - 2001/3

Y1 - 2001/3

N2 - This paper considers the problem of computing the dense k-vertex subgraph of a given graph, namely, the subgraph with the most edges. An approximation algorithm is developed for the problem, with approximation ratio O(nδ), for some δ < 1/3.

AB - This paper considers the problem of computing the dense k-vertex subgraph of a given graph, namely, the subgraph with the most edges. An approximation algorithm is developed for the problem, with approximation ratio O(nδ), for some δ < 1/3.

KW - Approximation algorithms

KW - Dense subgraph

UR - http://www.scopus.com/inward/record.url?scp=0005259971&partnerID=8YFLogxK

U2 - 10.1007/s004530010050

DO - 10.1007/s004530010050

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:0005259971

SN - 0178-4617

VL - 29

SP - 410

EP - 421

JO - Algorithmica

JF - Algorithmica

IS - 3

ER -

The dense k-subgraph problem

ملخص

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

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

بصمة

قم بذكر هذا