On partitioning a graph into two connected subgraphs

DOI10.1016/j.tcs.2011.09.001zbMath1228.68032OpenAlexW2019800388MaRDI QIDQ650911

Daniël Paulusma, Johan M. M. van Rooij

Publication date: 7 December 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.09.001

zbMATH Keywords

dominating setexact algorithmdisjoint connected subgraphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

Solving the 2-disjoint connected subgraphs problem faster than \(2^n\) ⋮ Inclusion/exclusion meets measure and conquer ⋮ Disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ The Price of Connectivity in Fair Division

Cites Work

• Unnamed Item
• Unnamed Item
• Removing local extrema from imprecise terrains
• Inclusion and exclusion algorithm for the Hamiltonian path problem
• Solving connected dominating set faster than \(2^n\)
• A new characterization of \(P_{6}\)-free graphs
• On two techniques of combining branching and treewidth
• Partitioning graphs into connected parts
• Dynamic programming meets the principle of inclusion and exclusion
• The vertex separation and search number of a graph
• Graph minors. XIII: The disjoint paths problem
• Set Partitioning via Inclusion-Exclusion
• Inclusion/Exclusion Meets Measure and Conquer
• Combinatorial bounds via measure and conquer
• Automata, Languages and Programming

This page was built for publication: On partitioning a graph into two connected subgraphs