Probe Distance-Hereditary Graphs

Chang, M.-S., Hung, L.-J. and Rossmanith, P.

    A graph G = (V,E) is called a probe graph of graph class G if V can be partitioned into two sets P (probes) and N (nonprobes), where N is an independent set, such that G can be embedded into a graph of G by adding edges between certain nonprobes. A graph is distance hereditary if the distance between any two vertices remains the same in every connected induced subgraph. Distance-hereditary graphs have been studied by many researchers. In this paper we give an O(nm)-time algorithm for recognizing probe graphs of distance-hereditary graphs.
Cite as: Chang, M.-S., Hung, L.-J. and Rossmanith, P. (2010). Probe Distance-Hereditary Graphs. In Proc. 16-th Computing: The Australasian Theory Symposium (CATS 2010) Brisbane, Australia. CRPIT, 109. Viglas, T. and Potanin, A. Eds., ACS. 55-64
pdf (from pdf (local if available) BibTeX EndNote GS