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].
This website uses cookies
We use cookies to provide you with the best possible experience. They also allow us to analyze user behavior in order to constantly improve the website for you. Info about the privacy policy of IOS Press.
This website uses cookies
We use cookies to provide you with the best possible experience. They also allow us to analyze user behavior in order to constantly improve the website for you. Info about the privacy policy of IOS Press.