1 Citation (Scopus)

Abstract

Rectangle partitioning is one of the most common combinatorial problems which main purpose is to count possible configurations based on some given variables. Typical approach to solve this problem needs a polynomial time complexity, which leads to a new issue when time and memory is a crucial factor in this problem solving. One specific rectangular partitioning problem that has this issue is to count how many possible partitions can be done on a M×N rectangle to divide it into exactly two subregions. In this paper, we propose a novel solution for the aforementioned problem using dynamic programming with profile method, also known as broken profile DP. This broken profile DP method is famous for solving complex 2D grid problems by breaking it into some simpler subproblems and exploiting the special structure of the particular problem, which is referred as a profile. A disjoint-set data structure is used alongside with broken profile DP to validate each line configuration’s connectivity, since the DP transition is processed line-by-line. In the implementation later on, it is necessary to implement big integer in order to store very big values. Based on the case study testing result, the solution using broken profile dynamic programming method requires an average time of 0.0012 seconds and an average memory of 530 KiB.

Original languageEnglish
Article numberIJCS_49_2_15
JournalIAENG International Journal of Computer Science
Volume49
Issue number2
Publication statusPublished - 2022

Keywords

  • Broken profile
  • Disjoint-set data structure
  • Dynamic programming
  • Rectangle partitioning

Fingerprint

Dive into the research topics of 'Dynamic Programming Approach for Solving Rectangle Partitioning Problem'. Together they form a unique fingerprint.

Cite this