论文标题
在限制和弦和琐碎完美的图表中
On restricted completions of chordal and trivially perfect graphs
论文作者
论文摘要
令$ g $为具有顶点$ v $的图形，这样$ h = g -v $是一个琐碎的完美图。我们为确定是否可以将$ k $边缘添加到$ g $的问题以获取一个琐碎的完美图。这是经过良好研究的{\ sc edge Metterion}的略有变化，也称为{\ sc最小填充}，问题。我们还表明，如果$ h $是和弦图，那么决定是否可以将最多$ k $边缘添加到$ g $获得和弦图的问题是\ np complete。
Let $G$ be a graph having a vertex $v$ such that $H = G - v$ is a trivially perfect graph. We give a polynomial-time algorithm for the problem of deciding whether it is possible to add at most $k$ edges to $G$ to obtain a trivially perfect graph. This is a slight variation of the well-studied {\sc Edge Completion}, also known as {\sc Minimum Fill-In}, problem. We also show that if $H$ is a chordal graph, then the problem of deciding whether it is possible to add at most $k$ edges to $G$ to obtain a chordal graph is \NP-complete.
