Balanced connected partitioning of unweighted grid graphs

DOI10.4230/LIPICS.MFCS.2018.39MaRDI QIDQ5005141zbMATH OpenOpenAlexFDO

Authors Cedric Berenger, Peter Niebert, Kévin Perrot

Publication date 4 August 2021

Full work available at URL https://hal.science/hal-02093978

zbMATH Keywords

connected partitioninggraph algorithmgrid graphsNP-completeness

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Max-min partitioning of grid graphs into connected components
• Fast balanced partitioning is hard even on grids and trees
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• Fast balanced partitioning is hard even on grids and trees
• On finding connected balanced partitions of trees

Cites work

• Max-min partitioning of grid graphs into connected components

Cited in

(2)

• The painter's problem: covering a grid with colored connected polygons
• Reconfiguration of connected graph partitions

This page was built for publication: Balanced connected partitioning of unweighted grid graphs

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