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

https://hal.inria.fr/hal-00966503
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

File

713-2533-1-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00966503, version 1

Collections

Citation

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

Share

Metrics

Record views

102

Files downloads

966