License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2016.18
URN: urn:nbn:de:0030-drops-69438
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/6943/
Kobayashi, Yasuaki ;
Tamaki, Hisao
Treedepth Parameterized by Vertex Cover Number
Abstract
To solve hard graph problems from the parameterized perspective, structural parameters have commonly been used. In particular, vertex cover number is frequently used in this context. In this paper, we study the problem of computing the treedepth of a given graph G. We show that there are an O(tau(G)^3) vertex kernel and an O(4^{tau(G)}*tau(G)*n) time fixed-parameter algorithm for this problem, where tau(G) is the size of a minimum vertex cover of G and n is the number of vertices of G.
BibTeX - Entry
@InProceedings{kobayashi_et_al:LIPIcs:2017:6943,
author = {Yasuaki Kobayashi and Hisao Tamaki},
title = {{Treedepth Parameterized by Vertex Cover Number}},
booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
pages = {18:1--18:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-023-1},
ISSN = {1868-8969},
year = {2017},
volume = {63},
editor = {Jiong Guo and Danny Hermelin},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/6943},
URN = {urn:nbn:de:0030-drops-69438},
doi = {10.4230/LIPIcs.IPEC.2016.18},
annote = {Keywords: Fixed-parameter algorithm, Polynomial kernelization, Structural parameterization, Treedepth, Vertex cover}
}
|
Keywords: |
|
Fixed-parameter algorithm, Polynomial kernelization, Structural parameterization, Treedepth, Vertex cover |
|
Collection: |
|
11th International Symposium on Parameterized and Exact Computation (IPEC 2016) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
09.02.2017 |
