Kernelization using structural parameters on sparse graph classes
详细信息    查看全文
文摘
class="listitem" id="list_ls0010">
class="label">•

Meta-theorems for linear kernels have been the subject of intensive research.

class="label">•

We follow the line toward even larger graph classes using stronger parametrization.

class="label">•

FII problems have linear kernels on graphs of bounded expansion, parameterized by the size of a treedepth-modulator.

class="label">•

For nowhere dense classes, this yields almost-linear kernels.

class="label">•

FII is required only on graphs of bounded treedepth.

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700