On partitioning a graph into two connected subgraphs
DOI10.1016/J.TCS.2011.09.001zbMATH Open1228.68032OpenAlexW2019800388MaRDI QIDQ650911FDOQ650911
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
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph minors. XIII: The disjoint paths problem
- Automata, Languages and Programming
- On two techniques of combining branching and treewidth
- Combinatorial bounds via measure and conquer
- Set Partitioning via Inclusion-Exclusion
- Partitioning graphs into connected parts
- The vertex separation and search number of a graph
- A new characterization of \(P_{6}\)-free graphs
- Solving connected dominating set faster than \(2^n\)
- Inclusion/Exclusion Meets Measure and Conquer
- Removing local extrema from imprecise terrains
- Dynamic programming meets the principle of inclusion and exclusion
- Inclusion and exclusion algorithm for the Hamiltonian path problem
Cited In (12)
- Partitioning a graph into two pieces, each isomorphic to the other or to its complement
- On partitioning the edges of graphs into connected subgraphs
- On the complexity of partitioning graphs into connected subgraphs
- ON TWO GRAPH PARTITIONING QUESTIONS
- Graphs without a partition into two proportionally dense subgraphs
- Partitioning a graph into complementary subgraphs
- The Price of Connectivity in Fair Division
- Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
- Title not available (Why is that?)
- Disjoint paths and connected subgraphs for \(H\)-free graphs
- Disjoint paths and connected subgraphs for \(H\)-free graphs
- Inclusion/exclusion meets measure and conquer
Recommendations
- Title not available (Why is that?) 👍 👎
- On the complexity of partitioning graphs into connected subgraphs 👍 👎
- Partitioning graphs into connected parts 👍 👎
- On the complexity of partitioning a graph into a few connected subgraphs 👍 👎
- On partitioning the edges of graphs into connected subgraphs 👍 👎
- On Partitioning a Graph into Two Connected Subgraphs 👍 👎
- Partitioning a Graph into Highly Connected Subgraphs 👍 👎
- Partitioning Graphs into Connected Parts 👍 👎
- Partitioning a k-connected graph 👍 👎
- A partition of connected graphs 👍 👎
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)
