Partitioning Graphs into Connected Parts

DOI10.1007/978-3-642-03351-3_15MaRDI QIDQ3392949zbMATH OpenOpenAlexFDO

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

Publication date 18 August 2009

Published in Computer Science - Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03351-3_15

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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 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
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• 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

(15)

• Partitioning ℝ^<em>n</em> into Connected Components
• Path Contraction Faster Than 2^n
• Finding part-machine families using graph partitioning techniques
• On partitioning a graph into two connected subgraphs
• On partitioning the edges of graphs into connected subgraphs
• Finding contractions and induced minors in chordal graphs via disjoint paths
• Path contraction faster than \(2^n\)
• Partitioning graphs into connected parts
• Partitioning a graph into minimum gap components
• Partitioning multi-edge graphs
• On partitioning a graph into two connected subgraphs
• scientific article; zbMATH DE number 7101993 (Why is no real title available?)
• Partitioning graphs into complete and empty graphs
• Structured proportional representation
• The parameterized complexity landscape of finding 2-partitions of digraphs

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 Q3392949)