Editing to Eulerian graphs

作者：

Highlights：

• We prove that editing to Eulerian graphs is polynomial-time solvable.

• We prove the same result for directed graphs.

• We fully classify the complexity of two generalizations of this problem.

• We classify variants where vertex deletions are additionally permitted.

摘要

•We prove that editing to Eulerian graphs is polynomial-time solvable.•We prove the same result for directed graphs.•We fully classify the complexity of two generalizations of this problem.•We classify variants where vertex deletions are additionally permitted.

论文关键词：Eulerian graphs,Graph editing,Polynomial algorithm

论文评审过程：Received 25 October 2014, Revised 11 September 2015, Accepted 9 October 2015, Available online 11 November 2015, Version of Record 27 November 2015.

论文官网地址：https://doi.org/10.1016/j.jcss.2015.10.003