Skip to Main content Skip to Navigation
Journal articles

Probe split graphs

Abstract : An undirected graph G=(V,E) is a probe split graph if its vertex set can be partitioned into two sets, N (non-probes) and P (probes) where N is independent and there exists E' ⊆ N× N such that G'=(V,E∪ E') is a split graph. Recently Chang et al. gave an O(V4(V+E)) time recognition algorithm for probe split graphs. In this article we give O(V2+VE) time recognition algorithms and characterisations by forbidden induced subgraphs both for the case when the partition into probes and non-probes is given, and when it is not given.
Document type :
Journal articles
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Wednesday, March 26, 2014 - 4:59:19 PM
Last modification on : Friday, November 23, 2018 - 3:38:02 PM
Long-term archiving on: : Thursday, June 26, 2014 - 11:55:14 AM


Files produced by the author(s)


  • HAL Id : hal-00966503, version 1



van Bang Le, H. N. Ridder. Probe split graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2007, 9 (1), pp.207--238. ⟨hal-00966503⟩



Record views


Files downloads