The Library
Solving the 2-Disjoint connected subgraphs problem faster than 2n
Tools
Tools
Tools
Cygan, Marek, Pilipczuk, Marcin, Pilipczuk, Michał and Wojtaszczyk, Jakub Onufry (2013) Solving the 2-Disjoint connected subgraphs problem faster than 2n. Algorithmica, Volume 70 (Number 2). pp. 195-207. doi:10.1007/s00453-013-9796-x ISSN 0178-4617.
|
PDF (Creative Commons : Attribution 4.0)
WRAP_art%3A10.1007%2Fs00453-013-9796-x.pdf - Published Version - Requires a PDF viewer. Download (698Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/s00453-013-9796-x
Abstract
The 2-Disjoint Connected Subgraphs problem, given a graph along with two disjoint sets of terminals Z 1,Z 2, asks whether it is possible to find disjoint sets A 1,A 2, such that Z 1⊆A 1, Z 2⊆A 2 and A 1,A 2 induce connected subgraphs. While the naive algorithm runs in O(2 n n O(1)) time, solutions with complexity of form O((2−ε) n ) have been found only for special graph classes (van ’t Hof et al. in Theor. Comput. Sci. 410(47–49):4834–4843, 2009; Paulusma and van Rooij in Theor. Comput. Sci. 412(48):6761–6769, 2011). In this paper we present an O(1.933 n ) algorithm for 2-Disjoint Connected Subgraphs in general case, thus breaking the 2 n barrier. As a counterpoise of this result we show that if we parameterize the problem by the number of non-terminal vertices, it is hard both to speed up the brute-force approach and to find a polynomial kernel.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
| Library of Congress Subject Headings (LCSH): | Graph theory, Kernel functions | ||||||||
| Journal or Publication Title: | Algorithmica | ||||||||
| Publisher: | Springer Verlag | ||||||||
| ISSN: | 0178-4617 | ||||||||
| Official Date: | 14 May 2013 | ||||||||
| Dates: |
|
||||||||
| Volume: | Volume 70 | ||||||||
| Number: | Number 2 | ||||||||
| Number of Pages: | 13 | ||||||||
| Page Range: | pp. 195-207 | ||||||||
| DOI: | 10.1007/s00453-013-9796-x | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||||||
| Date of first compliant deposit: | 28 December 2015 | ||||||||
| Date of first compliant Open Access: | 28 December 2015 | ||||||||
| Funder: | Narodowe Centrum Nauki (NCN), Fundacja na rzecz Nauki Polskiej [Foundation for Polish Science] (FNP), United States. Office of Naval Research, European Research Council (ERC) | ||||||||
| Grant number: | N206567140 (NCN), N000141110662 (ONR YIP), N206491038 (NCN), 267959 (ERC), N206567140 (NCN) |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
