Partitioning Graphs into Connected Parts

DOI10.1007/978-3-642-03351-3_15zbMath1248.68393OpenAlexW1532861364MaRDI QIDQ3392949

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

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

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) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Structured proportional representation ⋮ The parameterized complexity landscape of finding 2-partitions of digraphs

Cites Work

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

This page was built for publication: Partitioning Graphs into Connected Parts