A characterization of chain probe graphs

A characterization of chain probe graphs

0.00 Avg rating—0 Votes
Article ID: iaor20117905
Volume: 188
Issue: 1
Start Page Number: 175
End Page Number: 183
Publication Date: Aug 2011
Journal: Annals of Operations Research
Authors: , ,
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.

Reviews

Required fields are marked *. Your email address will not be published.