Partitioning graphs into connected parts

DOI10.1016/J.TCS.2009.06.028MaRDI QIDQ1034603zbMATH OpenOpenAlexFDO

Authors Pim Van 't Hof, Daniël Paulusma, Gerhard J. Woeginger

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

zbMATH Keywords

graph partitionexact algorithmedge contractionpath

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• Partitioning Graphs into Connected Parts
• On partitioning a graph into two connected subgraphs
• 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\)

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?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• A new characterization of \(P_{6}\)-free graphs
• Contractibility and NP-completeness
• Graph minors. XIII: The disjoint paths problem
• On the stable set problem in special \(P_{5}\)-free graphs
• Solving connected dominating set faster than \(2^n\)
• Stable sets in certain \(P_6\)-free graphs
• The complexity of coloring graphs without long induced paths

Cited in

(33)

• Connected vertex cover for \((sP_1+P_5)\)-free graphs
• Detecting fixed patterns in chordal graphs in polynomial time
• Partitioning ℝ^<em>n</em> into Connected Components
• Solving the 2-disjoint connected subgraphs problem faster than \(2^{n }\)
• Path Contraction Faster Than 2^n
• Finding part-machine families using graph partitioning techniques
• Removing local extrema from imprecise terrains
• The computational complexity of disconnected cut and \(2 K_2\)-partition
• On partitioning a graph into two connected subgraphs
• On partitioning the edges of graphs into connected subgraphs
• Finding good 2-partitions of digraphs. I. Hereditary properties
• Path contraction faster than \(2^n\)
• Degree-constrained 2-partitions of graphs
• Partitioning Graphs into Connected Parts
• Contracting bipartite graphs to paths and cycles
• Partitioning a graph into minimum gap components
• Increasing the minimum degree of a graph by contractions
• Increasing the minimum degree of a graph by contractions
• Detecting induced minors in AT-free graphs
• Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
• Partitioning multi-edge graphs
• On partitioning a graph into two connected subgraphs
• Priced gerrymandering
• Contracting bipartite graphs to paths and cycles
• scientific article; zbMATH DE number 7101993 (Why is no real title available?)
• Partitioning graphs into complete and empty graphs
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs
• Finding good 2-partitions of digraphs. II. Enumerable properties
• On the parameterized complexity of 2-partitions
• The price of connectivity in fair division

This page was built for publication: Partitioning graphs into connected parts

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