Paulusma, Daniel and van Rooij , J. M. M. (2009) 'On partitioning a graph into two connected subgraphs.', in *Algorithms and computation : 20th International Symposium, ISAAC 2009, 16-18 December 2009, Honolulu, Hawaii, USA ; proceedings.* Berlin: Springer, pp. 1215-1224. Lecture notes in computer science. (5878).

## Abstract

Suppose a graph G is given with two vertex-disjoint sets of vertices Z₁ and Z₂. Can we partition the remaining vertices of G such that we obtain two connected vertex-disjoint subgraphs of G that contain Z₁ and Z₂, respectively? This problem is known as the 2-Disjoint Connected Subgraphs problem. It is already NP-complete for the class of n-vertex graphs G = (V,E) in which Z₁ and Z₂ each contain a connected set that dominates all vertices in V\(Z₁ ∪ Z₂). We present an O^*(1.2051^n) time algorithm that solves it for this graph class. As a consequence, we can also solve this problem in O^*(1.2051^n) time for the classes of n-vertex P 6-free graphs and split graphs. This is an improvement upon a recent O^* (1.5790^n) time algorithm for these two classes. Our approach translates the problem to a generalized version of hypergraph 2-coloring and combines inclusion/exclusion with measure and conquer.

Item Type: | Book chapter |
---|---|

Full text: | Full text not available from this repository. |

Publisher Web site: | http://dx.doi.org/10.1007/978-3-642-10631-6_122 |

Record Created: | 15 Dec 2009 11:35 |

Last Modified: | 03 Apr 2013 13:12 |

Social bookmarking: | Export: EndNote, Zotero | BibTex |

Usage statistics | Look up in GoogleScholar | Find in a UK Library |