A polynomial kernel for trivially perfect editing

DOI10.1007/S00453-017-0401-6MaRDI QIDQ6827816zbMATH OpenFDO

Authors Pål Grønås Drange, Michał Pilipczuk

Publication date 18 October 2018

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00453-017-0401-6

zbMATH Keywords

graph modificationpolynomial kerneltrivially perfect graph

Mathematics Subject Classification ID

Perfect graphs (05C17) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Cited in

(5)

• An improved kernelization algorithm for trivially perfect editing
• Parameterized complexity of biclique contraction and balanced biclique contraction
• Polynomial kernels for edge modification problems towards block and strictly chordal graphs
• Parameterized dynamic data structure for split completion
• A finer view of the parameterized landscape of labeled graph contractions

This page was built for publication: A polynomial kernel for trivially perfect editing

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