Counting Rectangular Drawings or Floorplans in Polynomial Time

スポンサーリンク

概要

• 論文の詳細を見る

• 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 ≤ 3000.

• （社）電子情報通信学会の論文
• 2009-04-01

著者

• Inoue Youhei

  Renesas Technology Corp.

• TAKAHASHI Toshihiko

  Institute of Natural Science and Technology, Academic Assembly, Niigata University

• FUJIMAKI Ryo

  Graduate School of Science and Technology, Niigata University

• Fujimaki Ryo

  Graduate School Of Science And Technology Niigata University

• Takahashi Toshihiko

  Institute Of Natural Science And Technology Academic Assembly Niigata University

関連論文

• Counting Rectangular Drawings or Floorplans in Polynomial Time
• Fujimaki-Takahashi Squeeze : Linear Time Construction of Constraint Graphs of Floorplan for a Given Permutation
• A Surjective Mapping from Permutations to Room-to-Room Floorplans(Selected Papers from the 19th Workshop on Circuits and Systems in Karuizawa)

スポンサーリンク