|
|
|
|
complexity and approximation ratio of semitotal domination in graphs
|
|
|
|
|
|
|
|
نویسنده
|
shao zehui ,wu pu
|
|
منبع
|
communications in combinatorics and optimization - 2018 - دوره : 3 - شماره : 2 - صفحه:143 -150
|
|
چکیده
|
A set s ⊆ v (g) is a semitotal dominating set of a graph g if it is adominating set of g and every vertex in s is within distance 2 of another vertex of s. the semitotal domination number γt₂(g) is the minimum cardinality of a semitotal dominating set of g. we show that the semitotal domination problem is apx-complete for bounded-degree graphs, and the semitotal domination problem in any graph of maximum degree ∆ can be approximated with an approximation ratio of 2 +ln(∆− 1).
|
|
کلیدواژه
|
semitotal domination ,apx-complete ,np-completeness
|
|
آدرس
|
guangzhou university, institute of computing science and technology, china, guangzhou university, institute of computing science and technology, china
|
|
پست الکترونیکی
|
wupu@mail.cdu.edu.cn
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|