Tree-depth and Vertex-minors

• Autoři: HLINĚNÝ Petr; KWON O-joung; OBDRŽÁLEK Jan; ORDYNIAK Sebastian
• Rok publikování: 2016
• Druh: Článek v odborném periodiku
• Časopis / Zdroj: European Journal of Combinatorics
• Fakulta / Pracoviště MU: Fakulta informatiky
• Doi: http://dx.doi.org/10.1016/j.ejc.2016.03.001
• Obor: Informatika
• Klíčová slova: tree-depth; shrub-depth; vertex-minor; pivot-minor
• Popis: Dokazujeme, že každou třída grafů omezené shrub-depth lze získat pomocí vrcholových minorů z třídy omezené tree-depth. V obecnosti toto neplatí pro pivot minory.

Související projekty

• Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky