Good characterizations and linear time recognition for 2-probe block graphs.

Block graphs are graphs in which every block (biconnected component) is a clique. A graph G = ( V , E ) is said to be an (unpartitioned) k -probe block graph if there exist k independent sets N i ⊆ V , 1 ≤ i ≤ k , such that the graph G ′ obtained from G by adding certain edges between vertices inside the sets N i , 1 ≤ i ≤ k , is a block graph; if the independent sets N i are given, G is called a partitioned k -probe block graph. In this paper we give good characterizations for 2 -probe block graphs, in both unpartitioned and partitioned cases. As an algorithmic implication, partitioned and unpartitioned probe block graphs can be recognized in linear time, improving a recognition algorithm of cubic time complexity previously obtained by Chang et al. (2011). [ABSTRACT FROM AUTHOR]