A characterization of chain probe graphs

被引：7
作者：
Golumbic, Martin C. [1 ,3 ,4 ]
Maffray, Frederic [2 ]
Morel, Gregory
机构：
[1] Univ Haifa, Caesarea Rothschild Inst & Dept Comp Sci, Haifa, Israel
[2] CNRS, Lab G SCOP, Grenoble, France
[3] Univ Haifa, Caesarea Rothschild Inst, IL-31999 Haifa, Israel
[4] Univ Haifa, Dept Comp Sci, IL-31999 Haifa, Israel
来源：
ANNALS OF OPERATIONS RESEARCH | 2011年 / 188卷 / 01期
关键词：
RECOGNITION;
D O I：
10.1007/s10479-009-0584-6
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
A chain probe graph is a graph that admits an independent set S of vertices and a set F of pairs of elements of S such that G+F is a chain graph (i.e., a 2K (2)-free bipartite graph). We show that chain probe graphs are exactly the bipartite graphs that do not contain as an induced subgraph a member of a family of six forbidden subgraphs, and deduce an O(n (2)) recognition algorithm.
引用
收藏
页码：175 / 183
页数：9
相关论文
共 24 条
[1]  
BERRY A, 2004, P 15 ACM SIAM S DISC, P962
[2]   Recognizing chordal probe graphs and cycle-bicolorable graphs [J].
Berry, Anne ;
Golumbic, Martin Charles ;
Lipshteyn, Marina .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2007, 21 (03) :573-591
[3]  
Brandstadt A., 1999, SIAM MONOG DISCR MAT
[4]  
Chandler DB, 2008, LECT NOTES COMPUT SC, V5092, P468
[5]  
Chang MS, 2005, LECT NOTES COMPUT SC, V3595, P808, DOI 10.1007/11533719_82
[6]  
Chvatal<prime> V., 1977, Ann. Discrete Math., V1, P145
[7]  
Golumbic M. C., 2004, Tolerance Graphs
[8]  
Golumbic M.C., 2004, ANN DISCRETE MATH, V57
[9]  
Golumbic MC, 2003, LECT NOTES COMPUT SC, V2880, P249
[10]   Chordal probe graphs [J].
Golumbic, MC ;
Lipshteyn, M .
DISCRETE APPLIED MATHEMATICS, 2004, 143 (1-3) :221-237
123