Thin graph classes and polynomial-time approximation schemes

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
Thin graph classes and polynomial-time approximation schemes
Original language description
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'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.
Czech name
—
Czech description
—

Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

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

Article name in the collection
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms
ISBN
978-1-61197-503-1
ISSN
—
e-ISSN
neuvedeno
Number of pages
17
Pages from-to
1685-1701
Publisher name
Society for Industrial and Applied Mathematics
Place of publication
Philadelphia, PA, USA
Event location
New Orleans, LA, USA
Event date
Jan 7, 2018
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)