Thin graph classes and polynomial-time approximation schemes

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10385420" target="_blank" >RIV/00216208:11320/18:10385420 - isvavai.cz</a>

Výsledek na webu

<a href="https://epubs.siam.org/doi/10.1137/1.9781611975031.110" target="_blank" >https://epubs.siam.org/doi/10.1137/1.9781611975031.110</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/1.9781611975031.110" target="_blank" >10.1137/1.9781611975031.110</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Thin graph classes and polynomial-time approximation schemes

Popis výsledku v původním jazyce

Baker [1] devised a powerful technique to obtain approximation schemes for various problems restricted to planar graphs. Her technique can be directly extended to various other graph classes, among the most general ones the graphs avoiding a fixed apex graph as a minor. Further generalizations (e.g., to all proper minor closed graph classes) are known, but they use a combination of techniques and usually focus on somewhat restricted classes of problems. We present a new type of graph decompositions (thin systems of overlays) generalizing Baker&apos;s technique and leading to straightforward polynomial-time approximation schemes. We also show that many graph classes (all proper minor-closed classes, and all subgraph-closed classes with bounded maximum degree and strongly sublinear separators) admit such decompositions.

Název v anglickém jazyce

Thin graph classes and polynomial-time approximation schemes

Popis výsledku anglicky

Baker [1] devised a powerful technique to obtain approximation schemes for various problems restricted to planar graphs. Her technique can be directly extended to various other graph classes, among the most general ones the graphs avoiding a fixed apex graph as a minor. Further generalizations (e.g., to all proper minor closed graph classes) are known, but they use a combination of techniques and usually focus on somewhat restricted classes of problems. We present a new type of graph decompositions (thin systems of overlays) generalizing Baker&apos;s technique and leading to straightforward polynomial-time approximation schemes. We also show that many graph classes (all proper minor-closed classes, and all subgraph-closed classes with bounded maximum degree and strongly sublinear separators) admit such decompositions.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2018

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms

ISBN

978-1-61197-503-1

ISSN

—

e-ISSN

neuvedeno

Počet stran výsledku

17

Strana od-do

1685-1701

Název nakladatele

Society for Industrial and Applied Mathematics

Místo vydání

Philadelphia, PA, USA

Místo konání akce

New Orleans, LA, USA

Datum konání akce

7. 1. 2018

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—