GANIAN, Robert, Eduard EIBEN a 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, s. "34:1"-"34:14", 14 s. ISBN 978-3-95977-016-3. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.MFCS.2016.34. |
Další formáty:
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 a 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, s.~''34:1''-''34:14'', 14 s. ISBN~978-3-95977-016-3. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.MFCS.2016.34.
|