| GANIAN, Robert, Eduard EIBEN and O-joung KWON. A Single-Exponential Fixed-Parameter Algorithm for Distance-Hereditary Vertex Deletion. Online. In Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier. 41st International Symposium on Mathematical Foundations of Computer Science, {MFCS} 2016, August 22-26, 2016 - Krak{\'{o}}w, Poland. Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. p. "34:1"-"34:14", 14 pp. ISBN 978-3-95977-016-3. Available from: https://dx.doi.org/10.4230/LIPIcs.MFCS.2016.34. [citováno 2024-04-24] |
Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1376048,
author = {Ganian, Robert and Eiben, Eduard and Kwon, Oandjoung},
address = {Germany},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science, {MFCS} 2016, August 22-26, 2016 - Krak{\'{o}}w, Poland},
doi = {http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.34},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
keywords = {algorithms; vertex deletion problems},
howpublished = {elektronická verze "online"},
language = {eng},
location = {Germany},
isbn = {978-3-95977-016-3},
pages = {"34:1"-"34:14"},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
title = {A Single-Exponential Fixed-Parameter Algorithm for Distance-Hereditary Vertex Deletion},
year = {2016}
}
TY - JOUR
ID - 1376048
AU - Ganian, Robert - Eiben, Eduard - Kwon, O-joung
PY - 2016
TI - A Single-Exponential Fixed-Parameter Algorithm for Distance-Hereditary Vertex Deletion
PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
CY - Germany
SN - 9783959770163
KW - algorithms
KW - vertex deletion problems
N2 - Vertex deletion problems ask whether it is possible to delete at most k vertices from a graph so that the resulting graph belongs to a specified graph class. Over the past years, the parameterized complexity of vertex deletion to a plethora of graph classes has been systematically researched. Here we present the first single-exponential fixed-parameter algorithm for vertex deletion to distance-hereditary graphs, a well-studied graph class which is particularly important in the context of vertex deletion due to its connection to the graph parameter rank-width. We complement our result with matching asymptotic lower bounds based on the exponential time hypothesis.
ER -
GANIAN, Robert, Eduard EIBEN and O-joung KWON. A Single-Exponential Fixed-Parameter Algorithm for Distance-Hereditary Vertex Deletion. Online. In Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier. \textit{41st International Symposium on Mathematical Foundations of Computer Science, $\{$MFCS$\}$ 2016, August 22-26, 2016 - Krak$\{\backslash$'$\{$o$\}\}$w, Poland}. Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. p.~''34:1''-''34:14'', 14 pp. ISBN~978-3-95977-016-3. Available from: https://dx.doi.org/10.4230/LIPIcs.MFCS.2016.34. [citováno 2024-04-24]
|
