A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion

DOI10.4230/LIPICS.MFCS.2016.34MaRDI QIDQ4608593zbMATH OpenOpenAlexFDO

Authors Eduard Eiben, Robert Ganian, O-joung Kwon

Publication date 21 March 2018

Full work available at URL http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.34

zbMATH Keywords

fixed-parameter algorithmsrank-widthdistance-hereditary graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Structural characterization of families of graphs (05C75)

Recommendations

• A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
• Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
• A polynomial kernel for distance-hereditary vertex deletion
• A polynomial kernel for distance-hereditary vertex deletion
• Parameterized vertex deletion problems for hereditary graph classes with a block property

Cited in

(4)

• Distance from triviality 2.0: hybrid parameterizations
• A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
• A polynomial kernel for distance-hereditary vertex deletion
• An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion

This page was built for publication: A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608593)