The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Une subdivision d'un rectangle en faces rectangulaires avec des segments de lignes horizontales et verticales est appelée dessin rectangulaire ou plan d'étage. Il a été un problème ouvert de déterminer s'il existe un algorithme de temps polynomial pour calculer R(n). Nous résolvons le problème de manière affirmative, c'est-à-dire que nous introduisons un O(n4)-temps et O(n3)-algorithme d'espace pour R(n). L'algorithme est basé sur une récurrence pour R(n), qui est le résultat principal de cet article. Nous implémentons également notre algorithme et calculons R(n) Pour n
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Youhei INOUE, Toshihiko TAKAHASHI, Ryo FUJIMAKI, "Counting Rectangular Drawings or Floorplans in Polynomial Time" in IEICE TRANSACTIONS on Fundamentals,
vol. E92-A, no. 4, pp. 1115-1120, April 2009, doi: 10.1587/transfun.E92.A.1115.
Abstract: A subdivision of a rectangle into rectangular faces with horizontal and vertical line segments is called a rectangular drawing or floorplan. It has been an open problem to determine whether there exist a polynomial time algorithm for computing R(n). We affirmatively solve the problem, that is, we introduce an O(n4)-time and O(n3)-space algorithm for R(n). The algorithm is based on a recurrence for R(n), which is the main result of the paper. We also implement our algorithm and computed R(n) for n
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.1115/_p
Copier
@ARTICLE{e92-a_4_1115,
author={Youhei INOUE, Toshihiko TAKAHASHI, Ryo FUJIMAKI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Counting Rectangular Drawings or Floorplans in Polynomial Time},
year={2009},
volume={E92-A},
number={4},
pages={1115-1120},
abstract={A subdivision of a rectangle into rectangular faces with horizontal and vertical line segments is called a rectangular drawing or floorplan. It has been an open problem to determine whether there exist a polynomial time algorithm for computing R(n). We affirmatively solve the problem, that is, we introduce an O(n4)-time and O(n3)-space algorithm for R(n). The algorithm is based on a recurrence for R(n), which is the main result of the paper. We also implement our algorithm and computed R(n) for n
keywords={},
doi={10.1587/transfun.E92.A.1115},
ISSN={1745-1337},
month={April},}
Copier
TY - JOUR
TI - Counting Rectangular Drawings or Floorplans in Polynomial Time
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1115
EP - 1120
AU - Youhei INOUE
AU - Toshihiko TAKAHASHI
AU - Ryo FUJIMAKI
PY - 2009
DO - 10.1587/transfun.E92.A.1115
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E92-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 2009
AB - A subdivision of a rectangle into rectangular faces with horizontal and vertical line segments is called a rectangular drawing or floorplan. It has been an open problem to determine whether there exist a polynomial time algorithm for computing R(n). We affirmatively solve the problem, that is, we introduce an O(n4)-time and O(n3)-space algorithm for R(n). The algorithm is based on a recurrence for R(n), which is the main result of the paper. We also implement our algorithm and computed R(n) for n
ER -