Approximating minimum-cost connectivity problems

Guy Kortsarz, Zeev Nutov

פרסום מחקרי: פרק בספר / בדוח / בכנספרקביקורת עמיתים


We survey approximation algorithms and hardness results for versions of the Generalized Steiner Network (GSN) probleminwhichwe seek tofind a low-cost subgraph (where the cost of a subgraph is the sum of the costs of its edges) that satisfies prescribed connectivity requirements. These problems include the following well-known problems: min-cost k-flow, min-cost spanning tree, traveling salesman, directed/undirected Steiner tree, Steiner forest, k-edge/node-connected spanning subgraph, and others.

שפה מקוריתאנגלית
כותר פרסום המארחHandbook of Approximation Algorithms and Metaheuristics
מוציא לאורCRC Press
מסת"ב (אלקטרוני)9781420010749
מסת"ב (מודפס)1584885505, 9781584885504
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 ינו׳ 2007

הערה ביבליוגרפית

Publisher Copyright:
© 2007 by Taylor & Francis Group, LLC.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Approximating minimum-cost connectivity problems'. יחד הם יוצרים טביעת אצבע ייחודית.

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