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

DOI10.4230/LIPICS.MFCS.2016.34zbMATH Open1398.68228OpenAlexW3023645208MaRDI QIDQ4608593FDOQ4608593

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

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

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)

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)