D 2016

A Single-Exponential Fixed-Parameter Algorithm for Distance-Hereditary Vertex Deletion

GANIAN, Robert, Eduard EIBEN a O-joung KWON

Základní údaje

Originální název

A Single-Exponential Fixed-Parameter Algorithm for Distance-Hereditary Vertex Deletion

Autoři

GANIAN, Robert (203 Česká republika, garant, domácí), Eduard EIBEN (703 Slovensko) a O-joung KWON (410 Korejská republika)

Vydání

Germany, 41st International Symposium on Mathematical Foundations of Computer Science, {MFCS} 2016, August 22-26, 2016 - Krak{\'{o}}w, Poland, od s. "34:1"-"34:14", 14 s. 2016

Nakladatel

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Kód RIV

RIV/00216224:14330/16:00093948

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-016-3

ISSN

DOI

Klíčová slova anglicky

algorithms; vertex deletion problems

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 27. 8. 2019 12:08, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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.