Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F19%3A00113726" target="_blank" >RIV/00216224:14330/19:00113726 - isvavai.cz</a>
Result on the web
<a href="https://drops.dagstuhl.de/opus/volltexte/2019/10986/" target="_blank" >https://drops.dagstuhl.de/opus/volltexte/2019/10986/</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.MFCS.2019.42" target="_blank" >10.4230/LIPIcs.MFCS.2019.42</a>
Alternative languages
Result language
angličtina
Original language name
Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth
Original language description
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.
Czech name
—
Czech description
—
Classification
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)
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
ISBN
9783959771177
ISSN
1868-8969
e-ISSN
—
Number of pages
15
Pages from-to
1-15
Publisher name
Dagstuhl
Place of publication
Nemecko
Event location
Nemecko
Event date
Jan 1, 2019
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—