期刊论文

Yang, Xueying(yxycsust@163.com)

英文

计算机科学前沿(英文)

2095-2228

2023

17

4

174405-null

10.1007/s11704-022-2200-8

This work was supported by the Science and Education Joint Project of Hunan Natural Science Foundation (2021JJ60032), Research Foundation of Education Bureau of Hunan Province (21B0305), and Natural Science Foundation of Hunan Province of China (2022JJ30620).

本校为其他机构

In the minimum degree vertex deletion problem, we are given a graph, a distinguished vertex in the graph, and an integer κ, and the question is whether we can delete at most κ vertices from the graph so that the distinguished vertex has the unique minimum degree. The maximum degree vertex deletion problem is defined analogously but here we want the distinguished vertex to have the unique maximum degree. It is known that both problems are NP-hard and fixed-parameter intractable with respect to some natural parameters. In this paper, we study t...

In the minimum degree vertex deletion problem,we are given a graph,a distinguished vertex in the graph,and an ...展开更多 In the minimum degree vertex deletion problem,we are given a graph,a distinguished vertex in the graph,and an integer κ,and the question is whether we can delete at most κ vertices from the graph so that the distinguished vertex has the unique minimum degree.The maximum degree vertex deletion problem is defined analogously but here we want the distinguished vertex to have the unique maximum degree.It is known that both pro...