As a guest user you are not logged in or recognized by your IP address. You have
access to the Front Matter, Abstracts, Author Index, Subject Index and the full
text of Open Access publications.
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 , 1≤i≤k, such that the graph G′ obtained from G by adding some new edges between certain vertices inside the sets , 1≤i≤k, is a block graph; if the independent sets 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 2-probe block graphs can be recognized in linear time, improving a recognition algorithm of cubic time complexity previously obtained by Chang et al. (2011) in [3].