Parameterized complexity of Eulerian deletion problems

DOI10.1007/s00453-012-9667-xzbMath1284.05157WikidataQ37442987 ScholiaQ37442987MaRDI QIDQ2441593

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Dániel Marx, Ildikó Schlotter

Publication date: 25 March 2014

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9667-x

zbMATH Keywords

Eulerian graph; fixed-parameter tractability; kernelization; deletion distance

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W20: Randomized algorithms

05C45: Eulerian and Hamiltonian graphs