Separator Theorems for Interval Graphs and Proper Interval Graphs

被引：0

作者：

Panda, B. S. ^{[1
]}

机构：

[1] Indian Inst Technol Delhi, Dept Math, Comp Sci & Applicat Grp, New Delhi 110016, India

来源：

ALGORITHMS AND DISCRETE APPLIED MATHEMATICS (CALDAM 2015) | 2015年 / 8959卷

关键词：

Chordal Graphs; Interval Graphs; Proper Interval Graphs; INTERSECTION GRAPHS; PATHS; TREE;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

C.L. Monma and V.K. Wei [1986, J. Comb. Theory, Ser-B, 41, 141-181] proposed a unified approach to characterize several subclasses of chordal graphs using clique separator. The characterizations so obtained are called separator theorems. Separator theorems play an important role in designing algorithms in subclasses of chordal graphs. In this paper, we obtain separator theorems for interval graphs and proper interval graphs, which are subclasses of chordal graphs, following the framework of Monma and Wei.

引用

页码：101 / 110

页数：10

共 9 条

[1] CHARACTERIZATION OF COMPARABILITY GRAPHS + OF INTERVAL GRAPHS
GILMORE, PC
HOFFMAN, AJ
[J]. CANADIAN JOURNAL OF MATHEMATICS, 1964, 16 (03): : 539 - &
[2] Golumbic, 1980, ALGORITHMIC GRAPH TH
[3] Golumbic M.C., 1985, INTERVAL GRAPHS RELA, V55
[4] INTERSECTION GRAPHS OF PATHS IN A TREE
MONMA, CL
WEI, VK
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1986, 41 (02) : 141 - 181
[5] The forbidden subgraph characterization of directed vertex graphs
Panda, BS
[J]. DISCRETE MATHEMATICS, 1999, 196 (1-3) : 239 - 256
[6] INTERSECTION GRAPHS OF VERTEX DISJOINT PATHS IN A TREE
PANDA, BS
MOHANTY, SP
[J]. DISCRETE MATHEMATICS, 1995, 146 (1-3) : 179 - 209
[7] SCHEDULING INTERVAL-ORDERED TASKS
PAPADIMITRIOU, CH
YANNAKAKIS, M
[J]. SIAM JOURNAL ON COMPUTING, 1979, 8 (03) : 405 - 409
[8] Roberts F.S., 1976, DISCRETE MATH MODEL
[9] ROBERTS FS, 1971, PROOF TECHNIQUES GRA, P139

← 1 →