The dense k-subgraph problem

U. Feige, Guy 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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - מרץ 2001

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'The dense k-subgraph problem'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי