Informace o publikaci
Finite Integer Index of Pathwidth and Treewidth
| Autoři | |
|---|---|
| Rok publikování | 2014 |
| Druh | Článek ve sborníku |
| Konference | IPEC 2014, LNCS 8246 |
| Fakulta / Pracoviště MU | |
| Citace | |
| Doi | http://dx.doi.org/10.1007/978-3-319-13524-3_22 |
| Obor | Informatika |
| Klíčová slova | meta-kernalization; finite integer index; treewidth; pathwidth |
| Popis | We show that the optimization versions of the Pathwidth and Treewidth problems have a property called finite integer index when the inputs are restricted to graphs of bounded pathwidth and bounded treewidth, respectively. They do not have this property in general graph classes. This has interesting consequences for kernelization of both these (optimization) problems on certain sparse graph classes. In the process we uncover an interesting property of path and tree decompositions, which might be of independent interest. |
| Související projekty: |