Další formáty:
BibTeX
LaTeX
RIS
@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.
|
