Vi studerar flera problem med nätverksdesign med examensbegränsningar. För minimikostnaden Degree-Constraated 2-Node-Connected Subgraph problem, vi få den första icke-trivial bicriteria approximation algoritm, med 5b(v) + 3 överträdelse för examina och en 4- approximation för kostnaden. Detta förbättrar på logaritmisk grad överträdelse och ingen kostnadsgaranti som Feder, Motwani, och Zhu (2006). Sedan överväger vi problemet med att hitta en arborescens med åtminstone k-terminaler och med minimal maximal utgradering. Vi visar att den naturliga LP-avslappning har en lucka av.. ( ε k) eller (n 1/4 ) med avseende på multiplikativ grad bunden överträdelse. Vi övervinner detta hinder genom en kombinatorial O (k log k) / på * ) - approximationsalgoritm, där  till * betecknar den maximala graden i den optimala lösningen. Vi ger också en (log n) lägre gräns för att approximera detta problem. Sedan anser vi att den oriktade versionen av detta problem, dock med en extra diameter begränsning, och ge en "log n" lägre gräns på approximabiliteten av denna version. Vi anser också en nära relaterad Prize-Collecting DegreeConstomed Edge-Connectivity Survival Network problem, och få flera 6 En preliminär version av denna uppsats är [18]. E-postadresser: rohitk@us.ibm.com (Rohit Khandekar), guyk@camden.rutgers.edu (Guy Kortsarz), nutov@openu.ac.il (Zeev Nutov) Preprint inlämnad till Journal of Computer and System Sciences januari 12, 2013 resulterar i denna riktning genom att reducera prisinsamling varianten till den vanliga. Slutligen anser vi Terminal Steiner Tree problemet, som är en enkel variant av Degree-Constomed Steiner Tree problemet, när vissa terminaler krävs för att vara blad. Vi visar att detta till synes enkla problem är likvärdigt med problemet med gruppen Steiner Tree.
Minimum grad k-tree medger en O (k/-* ) log k)-uppskattning, där -* är den optimala graden och inte medger en o(log n)-uppskattning REF.
On some network design problems with degree constraints
{'venue': 'J. Comput. Syst. Sci.', 'journal': 'J. Comput. Syst. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}