Partitioning graphs into connected parts
From MaRDI portal
Publication:1034603
DOI10.1016/j.tcs.2009.06.028zbMath1194.68179OpenAlexW4213168420MaRDI QIDQ1034603
Daniël Paulusma, Gerhard J. Woeginger, Pim van 't Hof
Publication date: 6 November 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2009.06.028
Related Items
Increasing the Minimum Degree of a Graph by Contractions ⋮ Finding good 2-partitions of digraphs. I. Hereditary properties ⋮ Finding good 2-partitions of digraphs. II. Enumerable properties ⋮ Increasing the minimum degree of a graph by contractions ⋮ Detecting induced minors in AT-free graphs ⋮ Induced disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Induced disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Degree-constrained 2-partitions of graphs ⋮ Priced gerrymandering ⋮ Removing local extrema from imprecise terrains ⋮ On the parameterized complexity of 2-partitions ⋮ On partitioning a graph into two connected subgraphs ⋮ Solving the 2-disjoint connected subgraphs problem faster than \(2^n\) ⋮ Path Contraction Faster than $2^n$ ⋮ Detecting fixed patterns in chordal graphs in polynomial time ⋮ The computational complexity of disconnected cut and \(2 K_2\)-partition ⋮ Contracting bipartite graphs to paths and cycles ⋮ Connected vertex cover for \((sP_1+P_5)\)-free graphs ⋮ Contracting bipartite graphs to paths and cycles ⋮ Disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Path Contraction Faster Than 2^n ⋮ The Price of Connectivity in Fair Division
Cites Work
- Solving connected dominating set faster than \(2^n\)
- A new characterization of \(P_{6}\)-free graphs
- Stable sets in certain \(P_6\)-free graphs
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- On the stable set problem in special \(P_{5}\)-free graphs
- Graph minors. XIII: The disjoint paths problem
- Contractibility and NP-completeness
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
