On partitioning a graph into two connected subgraphs

DOI10.1016/J.TCS.2011.09.001MaRDI QIDQ650911zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• On partitioning a graph into two connected subgraphs
• On partitioning the edges of graphs into connected subgraphs
• On the complexity of partitioning graphs into connected subgraphs
• On the complexity of partitioning a graph into a few connected subgraphs
• Partitioning graphs into connected parts
• Partitioning Graphs into Connected Parts
• Partitioning a k-connected graph
• A partition of connected graphs
• Partitioning a graph into highly connected subgraphs
• scientific article; zbMATH DE number 7101993

Cites work

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

Cited in

(16)

• Partitioning Graphs into Connected Parts
• Inclusion/exclusion meets measure and conquer
• Graphs without a partition into two proportionally dense subgraphs
• Partitioning a graph into complementary subgraphs
• Partitioning a graph into two pieces, each isomorphic to the other or to its complement
• Partitioning graphs into connected parts
• On the complexity of partitioning graphs into connected subgraphs
• scientific article; zbMATH DE number 7101993 (Why is no real title available?)
• On partitioning the edges of graphs into connected subgraphs
• ON TWO GRAPH PARTITIONING QUESTIONS
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• Solving the 2-disjoint connected subgraphs problem faster than \(2^{n }\)
• Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
• On partitioning a graph into two connected subgraphs
• The price of connectivity in fair division

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q650911)