Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)

DOI10.1007/s00453-013-9796-xzbMath1306.05125OpenAlexW2126913088WikidataQ59399105 ScholiaQ59399105MaRDI QIDQ486988

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk

Publication date: 19 January 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-013-9796-x

zbMATH Keywords

exact algorithmsexponential time hypothesiskernelization\(2^n\) barrier2-disjoint connected subgraphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (9)

Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Enumeration of minimal tropical connected sets ⋮ Solving target set selection with bounded thresholds faster than \(2^n\) ⋮ Unnamed Item ⋮ Path Contraction Faster than $2^n$ ⋮ Solving Target Set Selection with Bounded Thresholds Faster than 2^n ⋮ Disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Path Contraction Faster Than 2^n

Cites Work

• Removing local extrema from imprecise terrains
• Exact exponential algorithms.
• On partitioning a graph into two connected subgraphs
• Exact and approximate bandwidth
• Partitioning graphs into connected parts
• Graph minors. XIII: The disjoint paths problem
• Connecting Terminals and 2-Disjoint Connected Subgraphs
• Exact Algorithm for the Maximum Induced Planar Subgraph Problem
• Scheduling Partially Ordered Jobs Faster Than 2 n
• A measure & conquer approach for the analysis of exact algorithms
• Fourier meets M\"{o}bius: fast subset convolution
• Set Partitioning via Inclusion-Exclusion
• Incompressibility through Colors and IDs
• Inclusion/Exclusion Meets Measure and Conquer
• The Complexity of Satisfiability of Small Depth Circuits
• On Problems as Hard as CNF-SAT
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• On the complexity of \(k\)-SAT
• Unnamed Item
• Unnamed Item

This page was built for publication: Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)