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: https://drops.dagstuhl.de/opus/volltexte/2017/6943/
Go to the corresponding LIPIcs Volume Portal


Kobayashi, Yasuaki ; Tamaki, Hisao

Treedepth Parameterized by Vertex Cover Number

pdf-format:
LIPIcs-IPEC-2016-18.pdf (0.4 MB)


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


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI