ON DOMINATION PROBLEMS FOR PERMUTATION AND OTHER GRAPHS

被引：49

作者：

BRANDSTADT, A

KRATSCH, D

机构：

[1] Friedrich-Schiller Univ Jena, Jena, East Ger, Friedrich-Schiller Univ Jena, Jena, East Ger

来源：

THEORETICAL COMPUTER SCIENCE | 1987年 / 54卷 / 2-3期

关键词：

COMPUTER PROGRAMMING - Algorithms;

D O I：

10.1016/0304-3975(87)90128-9

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

There is an increasing interest in results on the influence of restricting NP-complete graph problems, to special classes of perfect graphs as, e. g. , permutation graphs. In this paper we give (i) an algorithm with time bound O(n**2) for the weighted independent domination problem on permutation graphs (which is an improvement of the O(n**3) solution; (ii) a polynomial time solution for the weighted feedback vertex set problem on permutation graphs; (iii) an investigation of weighted dominating clique problems for several graph classes including an NP-completeness result for weakly triangulated graphs as well as polynomial time bounds.

引用

页码：181 / 198

页数：18

共 16 条

[1]

Berge C., 1973, GRAPHS HYPERGRAPHS, V7

[2]

BRANDSTADT A, 1985, LECT NOTES COMPUT SC, V199, P53

[3] FINDING MINIMUM DOMINATING CYCLES IN PERMUTATION GRAPHS [J].