Minimum fill-in of sparse graphs: kernelization and approximation

DOI10.1007/s00453-013-9776-1zbMath1310.68106WikidataQ60488431 ScholiaQ60488431MaRDI QIDQ2258069

Fedor V. Fomin, Yngve Villanger, Geevarghese Philip

Publication date: 2 March 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2011/3345/

zbMATH Keywords

planar graphs; parameterized complexity; kernelization; \(d\)-degenerate graphs; minimum fill-in; linear kernel

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C10: Planar graphs; geometric and topological aspects of graph theory

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms