A characterization of chain probe graphs |
| |
| Authors: | Martin C Golumbic Frédéric Maffray Grégory Morel |
| |
| Institution: | 1.Caesarea Rothschild Institute and Department of Computer Science,University of Haifa,Haifa,Israel;2.C.N.R.S.,Laboratoire G-SCOP,Grenoble,France;3.Laboratoire G-SCOP,Grenoble,France |
| |
| Abstract: | 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. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
