Partitioning graphs into connected parts

DOI10.1016/J.TCS.2009.06.028zbMATH Open1194.68179OpenAlexW4213168420MaRDI QIDQ1034603FDOQ1034603

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

zbMATH Keywords

graph partitionexact algorithmedge contractionpath

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Graph minors. XIII: The disjoint paths problem
• The complexity of coloring graphs without long induced paths
• Stable sets in certain \(P_6\)-free graphs
• A new characterization of \(P_{6}\)-free graphs
• Solving connected dominating set faster than \(2^n\)
• On the stable set problem in special \(P_{5}\)-free graphs
• Contractibility and NP-completeness

Cited In (30)

• 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
• Path Contraction Faster Than 2^n
• Finding part-machine families using graph partitioning techniques
• The computational complexity of disconnected cut and \(2 K_2\)-partition
• Removing local extrema from imprecise terrains
• Increasing the Minimum Degree of a Graph by Contractions
• On partitioning the edges of graphs into connected subgraphs
• Finding good 2-partitions of digraphs. I. Hereditary properties
• Degree-constrained 2-partitions of graphs
• Contracting bipartite graphs to paths and cycles
• Path Contraction Faster than $2^n$
• Partitioning a graph into minimum gap components
• Increasing the minimum degree of a graph by contractions
• Detecting induced minors in AT-free graphs
• The Price of Connectivity in Fair Division
• Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
• Priced gerrymandering
• Partitioning multi-edge graphs
• Contracting bipartite graphs to paths and cycles
• Title not available (Why is that?)
• On partitioning a graph into two connected subgraphs
• 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

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)