Measuring what Matters: A Hybrid Approach to Dynamic
Programming with Treewidth

D 2019

Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth

EIBEN, Eduard, Robert GANIAN, Thekla HAMM a O-joung KWON

Základní údaje

Originální název

Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth

Autoři

EIBEN, Eduard (703 Slovensko), Robert GANIAN (203 Česká republika, garant, domácí), Thekla HAMM (276 Německo) a O-joung KWON (410 Korejská republika)

Vydání

Nemecko, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), od s. 1-15, 15 s. 2019

Nakladatel

Dagstuhl

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Odkazy

URL

Kód RIV

RIV/00216224:14330/19:00113726

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-117-7

ISSN

DOI

http://dx.doi.org/10.4230/LIPIcs.MFCS.2019.42

Klíčová slova anglicky

Parameterized Complexity

Štítky

core_A, firank_A

Změněno: 14. 5. 2020 10:54, Mgr. Michal Petr

Anotace

V originále

We develop a framework for applying treewidth-based dynamic programming on graphs with "hybrid structure", i.e., with parts that may not have small treewidth but instead possess other structural properties. Informally, this is achieved by defining a refinement of treewidth which only considers parts of the graph that do not belong to a pre-specified tractable graph class. Our approach allows us to not only generalize existing fixed-parameter algorithms exploiting treewidth, but also fixed-parameter algorithms which use the size of a modulator as their parameter. As the flagship application of our framework, we obtain a parameter that combines treewidth and rank-width to obtain fixed-parameter algorithms for Chromatic Number, Hamiltonian Cycle, and Max-Cut.

Citovat

EIBEN, Eduard, Robert GANIAN, Thekla HAMM a O-joung KWON. Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth. Online. In Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen. 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Nemecko: Dagstuhl, 2019, s. 1-15. ISBN 978-3-95977-117-7. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.MFCS.2019.42.

@inproceedings{1648296,
   author = {Eiben, Eduard and Ganian, Robert and Hamm, Thekla and Kwon, Oandjoung},
   address = {Nemecko},
   booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
   doi = {http://dx.doi.org/10.4230/LIPIcs.MFCS.2019.42},
   editor = {Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
   keywords = {Parameterized Complexity},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Nemecko},
   isbn = {978-3-95977-117-7},
   pages = {1-15},
   publisher = {Dagstuhl},
   title = {Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth},
   url = {https://drops.dagstuhl.de/opus/volltexte/2019/10986/},
   year = {2019}
}

TY  - JOUR
ID  - 1648296
AU  - Eiben, Eduard - Ganian, Robert - Hamm, Thekla - Kwon, O-joung
PY  - 2019
TI  - Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth
PB  - Dagstuhl
CY  - Nemecko
SN  - 9783959771177
KW  - Parameterized Complexity
UR  - https://drops.dagstuhl.de/opus/volltexte/2019/10986/
L2  - https://drops.dagstuhl.de/opus/volltexte/2019/10986/
N2  - We develop a framework for applying treewidth-based dynamic programming on graphs with "hybrid structure", i.e., with parts that may not have small treewidth but instead possess other structural properties. Informally, this is achieved by defining a refinement of treewidth which only considers parts of the graph that do not belong to a pre-specified tractable graph class. Our approach allows us to not only generalize existing fixed-parameter algorithms exploiting treewidth, but also fixed-parameter algorithms which use the size of a modulator as their parameter. As the flagship application of our framework, we obtain a parameter that combines treewidth and rank-width to obtain fixed-parameter algorithms for Chromatic Number, Hamiltonian Cycle, and Max-Cut.
ER  -

EIBEN, Eduard, Robert GANIAN, Thekla HAMM a O-joung KWON. Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth. Online. In Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen. \textit{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}. Nemecko: Dagstuhl, 2019, s.~1-15. ISBN~978-3-95977-117-7. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.MFCS.2019.42.

Podrobný výpis o publikaci