A note on α-redundant vertices in graphs

被引：24

作者：

Brandstädt, A

Lozin, VV

机构：

[1] Univ Rostock, FB Informat, D-18051 Rostock, Germany

[2] Univ Nizhny Novgorod, Nizhnii Novgorod 603600, Russia

来源：

DISCRETE APPLIED MATHEMATICS | 2001年 / 108卷 / 03期

基金：

俄罗斯基础研究基金会;

关键词：

stable set; stability number; polynomial algorithm; alpha-redundant vertex; P-4; extension;

D O I：

10.1016/S0166-218X(00)00239-0

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A vertex v in a graph G is called alpha -redundant if alpha (G - v) = alpha (C), where alpha (G) stands for the stability number of G, i.e. the maximum size of a subset of pairwise nonadjacent vertices. We describe sufficient conditions for a vertex to be alpha -redundant in terms of some P-4 extensions. This leads to polynomial-time algorithms fur solving the stable set problem giving for an arbitrary input graph either the solution of the problem or a forbidden configuration such as an induced P-5 or an induced banner in the input graph. The algorithms extend and improve a number of previous results on the problem. (C) 2001 Elsevier Science B.V. All rights reserved.

引用

页码：301 / 308

页数：8

共 12 条

[1]

ALEKSEEV VE, 1979, CYBERNET PROBLEMS, V36, P23

[2]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[3] On the stability number of claw-free P5-free and more general graphs [J].