La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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

Counting Rectangular Drawings or Floorplans in Polynomial Time Compter des dessins rectangulaires ou des plans d'étage en temps polynomial

Youhei INOUE, Toshihiko TAKAHASHI, Ryo FUJIMAKI

  • Vues en texte intégral

    0

  • Citer

Résumé:

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

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.4 pp.1115-1120
Date de publication
2009/04/01
Publicisé
ISSN en ligne
1745-1337
DOI
10.1587/transfun.E92.A.1115
Type de manuscrit
Special Section PAPER (Special Section on Advanced Technologies Emerging Mainly from the 21st Workshop on Circuits and Systems in Karuizawa)
Catégories

Auteurs

Mots-clés

Table des matières