Partitioned probe comparability graphs

被引：7

作者：

Chandler, David B. ^{[2
]}

Chang, Maw-Shang ^{[3
]}

Kloks, Ton ^{[4
]}

Liu, Jiping ^{[5
]}

Peng, Sheng-Lung ^{[1
]}

机构：

[1] Natl Dong Hwa Univ, Dept Comp Sci & Informat Engn, Hualien 974, Taiwan

[2] Univ Delaware, Dept Math Sci, Newark, DE 19716 USA

[3] Natl Chung Cheng Univ, Dept Comp Sci & Informat Engn, Chiayi 621, Taiwan

[4] Univ Leeds, Sch Comp, Leeds LS2 9JT, W Yorkshire, England

[5] Univ Lethbridge, Dept Math & Comp Sci, Lethbridge, AB T1K 3M4, Canada

来源：

THEORETICAL COMPUTER SCIENCE | 2008年 / 396卷 / 1-3期

基金：

加拿大自然科学与工程研究理事会;

关键词：

graph recognition algorithms; probe graphs; comparability graphs; cocomparability graphs; permutation graphs;

D O I：

10.1016/j.tcs.2008.01.038

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Given a class of graphs g, a graph G is a probe graph of g if its vertices can be partitioned into a set of probes and an independent set of nonprobes such that G can be embedded into a graph of g by adding edges between certain nonprobes. If the partition of the vertices is part of the input, we call G a partitioned probe graph of g. In this paper we show that there exists a polynomial-time algorithm for the recognition of partitioned probe graphs of comparability graphs. This immediately leads to a polynomial-time algorithm for the recognition of partitioned probe graphs of cocomparability graphs. We then show that a partitioned graph G is a partitioned probe permutation graph if and only if G is at the same time a partitioned probe graph of comparability and cocomparability graphs. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：212 / 222

页数：11

共 23 条

[1]

[Anonymous], 1987, P 19 ANN ACM S THEOR

[2]

BERRY A, 2003, LIMOSRR0308

[3]

BERRY A, 2004, P 15 ACM SIAM S DISC, P962

[4]

Chandler DB, 2007, LECT NOTES COMPUT SC, V4508, P368

[5]

Chandler DB, 2006, LECT NOTES COMPUT SC, V3959, P494

[6]

Chandler DB, 2006, LECT NOTES COMPUT SC, V4041, P267

[7]

Chang GJ, 2005, LECT NOTES COMPUT SC, V3404, P521

[8]

CHANG GJ, 2005, ELECT NOTES DISCRETE, V7, P195

[9]

Chang MS, 2005, LECT NOTES COMPUT SC, V3595, P808, DOI 10.1007/11533719_82

[10]

Golumbic MC, 2003, LECT NOTES COMPUT SC, V2880, P249

← 1 2 3 →