ON THE VERTEX PACKING PROBLEM

被引：26

作者：

DESIMONE, C ^{[1
]}

机构：

[1] CNR, IST ANAL SISTEMI & INFORMAT, I-00185 ROME, ITALY

来源：

GRAPHS AND COMBINATORICS | 1993年 / 9卷 / 01期

关键词：

D O I：

10.1007/BF01195324

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A forbidden subgraphs characterization of the class of graphs that arise from bipartite graphs, odd holes, and graphs with no complement of a diamond via repeated substitutions is given. This characterization allows us to solve the vertex packing problem for the graphs in this class.

引用

页码：19 / 30

页数：12

共 13 条

[1]

Berge C., 1973, GRAPHS HYPERGRAPHS

[2]

BONDY JA, 1976, GRAPH THEORY APPLICA

[3] BULL-FREE BERGE GRAPHS ARE PERFECT [J].

CHVATAL, V ;

SBIHI, N .

GRAPHS AND COMBINATORICS, 1987, 3 (02) :127-139

[4]

DESIMONE C, 1989, IN PRESS DISCRETE AP

[5]

Garey M. R., 1976, Theoretical Computer Science, V1, P237, DOI 10.1016/0304-3975(76)90059-1

[6]

GROTSCHEL M, 1984, ANN DISCRETE MATH, V21, P325

[7] THE STRUCTION OF A GRAPH - APPLICATION TO CN-FREE GRAPHS [J].

HAMMER, PL ;

MAHADEV, NVR ;

DEWERRA, D .

COMBINATORICA, 1985, 5 (02) :141-147

[8] A POLYNOMIAL ALGORITHM FOR MAXIMUM WEIGHTED VERTEX PACKINGS ON GRAPHS WITHOUT LONG ODD CYCLES [J].

HSU, WL ;

IKURA, Y ;

NEMHAUSER, GL .

MATHEMATICAL PROGRAMMING, 1981, 20 (02) :225-232

[9]

Lovasz L, 1986, ANN DISCRETE MATH

[10] ON MAXIMAL INDEPENDENT SETS OF VERTICES IN CLAW-FREE GRAPHS [J].

MINTY, GJ .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1980, 28 (03) :284-304

← 1 2 →