Vi ger det första polynom-tids approximationssystemet (PTAS) för Steiners skogsproblem på plana grafer och, mer allmänt, på grafer av avgränsat släkte. Som ett första steg visar vi hur man bygger en Steiner-skogsnyckel för sådana grafer. Processens crux är ett klusterförfarande som kallas prissamlande kluster som bryter ner inmatnings instansen i separata subinstances som är lättare att hantera; dessutom är terminalerna i olika subinstances långt ifrån varandra. Varje subinstance har en relativt billig Steiner träd ansluter alla sina terminaler, och subinstances kan lösas (nästan) separat. Ett annat byggblock är ett PTAS för Steinerskog på grafer av avgränsad trädbredd. Förvånansvärt nog är Steinerskogen NP-hård även på grafer av trädbredd 3. Därför behöver våra PTAS för avgränsade trädbreddsdiagram en icke-trivial kombination av approximativa argument och dynamisk programmering på trädets nedbrytning. Vi visar vidare att Steiner skogen kan lösas i polynom tid för serieparallell grafer (grafer av trädbredd högst två) genom en ny kombination av dynamisk programmering och minimala skär beräkningar, slutföra vår grundliga komplexitet studie av Steiner skog i intervallet av avgränsade trädbredd grafer, planar grafer, och avgränsade släkten grafer. * För utelämnade bevis och vidare diskussion, se den fullständiga versionen av papper [6].
Bateni m.fl. I REF ges approximationssystem för det klassiska Steinerskogsproblemet på avgränsade grafer med trädbredd.
Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth
{'venue': "STOC '10", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}