Searching for better fill-in

作者：

Highlights：

• The k-Edge Connected Odd Subgraph problem is FPT when parameterized by k.

• The k-Vertex Eulerian Subgraph problem is W[1]-hard when parameterized by k.

• The treewidth of minimal connected odd graphs with minimal number of edges is at most three.

摘要

•The k-Edge Connected Odd Subgraph problem is FPT when parameterized by k.•The k-Vertex Eulerian Subgraph problem is W[1]-hard when parameterized by k.•The treewidth of minimal connected odd graphs with minimal number of edges is at most three.

论文关键词：Local search,Minimum fill-in,Parameterized complexity,Triangulation,Chordal graph

论文评审过程：Received 25 January 2013, Revised 18 February 2014, Accepted 4 April 2014, Available online 23 April 2014.

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