Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
On partitioning a graph into two connected subgraphs
Paulusma, D.; Rooij van, J. M. M.
Authors
J. M. M. Rooij van
Contributors
Y. Dong
Editor
D.-Z. Du
Editor
I. Ibarra
Editor
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.
Citation
Paulusma, D., & Rooij van, J. M. M. (2009). On partitioning a graph into two connected subgraphs. In Y. Dong, D. Du, & I. Ibarra (Eds.), Algorithms and computation : 20th International Symposium, ISAAC 2009, 16-18 December 2009, Honolulu, Hawaii, USA ; proceedings (1215-1224). https://doi.org/10.1007/978-3-642-10631-6_122
Conference Name | 20th International Symposium on Algorithms and Computation (ISAAC 2009) |
---|---|
Conference Location | Honolulu, Hawaii, United States |
Start Date | Dec 16, 2009 |
End Date | Dec 18, 2009 |
Publication Date | Dec 1, 2009 |
Deposit Date | Dec 15, 2009 |
Publisher | Springer Verlag |
Pages | 1215-1224 |
Series Title | Lecture notes in computer science. |
Series Number | 5878 |
Book Title | Algorithms and computation : 20th International Symposium, ISAAC 2009, 16-18 December 2009, Honolulu, Hawaii, USA ; proceedings. |
DOI | https://doi.org/10.1007/978-3-642-10631-6_122 |
Public URL | https://durham-repository.worktribe.com/output/1160345 |
Publisher URL | http://www.springerlink.com/content/u8740k7046427403/ |
You might also like
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
An algorithmic framework for locally constrained homomorphisms
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search