Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1016/j.jcss.2021.04.005 | Journal of Computer and System Sciences |
Keywords | DocType | Volume |
Parameterized complexity,Treewidth,Rank-width,Fixed-parameter algorithms | Journal | 121 |
ISSN | Citations | PageRank |
0022-0000 | 1 | 0.36 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eduard Eiben | 1 | 20 | 16.81 |
| Robert Ganian | 2 | 208 | 40.19 |
| Thekla Hamm | 3 | 1 | 1.71 |
| O-joung Kwon | 4 | 1 | 0.36 |