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

Planar Reconfiguration of Monotone Trees Reconfiguration planaire des arbres monotones

Yoshiyuki KUSAKARI, Masaki SATO, Takao NISHIZEKI

  • Vues en texte intégral

    0

  • Citer

Résumé:

Une liaison est un ensemble de segments de ligne, appelés barres, éventuellement joints à leurs extrémités, appelés joints. Une reconfiguration planaire d'une liaison est un mouvement continu de leurs barres, préservant la longueur de chaque barre et interdisant aux barres de se croiser. Dans cet article, nous introduisons une classe de liaisons, appelées « arbres monotones », et donnons une méthode pour reconfigurer un arbre monotone en ligne droite. Si l'arbre a n articulations, alors la méthode prend au plus n-1 mouvements, dont chacun utilise deux articulations. On obtient également un algorithme pour trouver une telle méthode dans le temps O(n log n), en utilisant l'espace O(n). Ces complexités temporelles et spatiales sont optimales.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.5 pp.938-943
Date de publication
2002/05/01
Publicisé
ISSN en ligne
DOI
Type de manuscrit
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Catégories

Auteurs

Mots-clés

Table des matières