PQ træ

Et PQ-træ  er en datastruktur til at repræsentere en permutationsgruppe . Dette er et plant træ med rod . De dinglende hjørner i den repræsenterer permutable elementer. Resten af ​​hjørnerne er mærket med enten , eller . Markerede hjørner har mindst 3 børn, og markerede hjørner har mindst 2 børn. I et PQ-træ er det tilladt at omarrangere efterkommerne af et toppunkt markeret vilkårligt og vende rækkefølgen af ​​efterkommerne af et toppunkt markeret .

PQ-træer bruges til at finde permutationer, hvis begrænsninger kendes gradvist, én efter én. Sådanne problemer opstår, når man genskaber DNA og kontrollerer planheden af ​​en graf.

Artikler

• Booth, Kellogg S. og Lueker, George S. Test af de fortløbende egenskaber, intervalgrafer og grafplanaritet ved hjælp af PQ-træalgoritmer  //  Journal of Computer and System Sciences. - 1976. - Bd. 13 , nr. 3 . — S. 335–379 . - doi : 10.1016/S0022-0000(76)80045-1 .
• Shih, Wei-Kuan og Hsu, Wen-Lian. En ny planaritetstest  (engelsk)  // Theoretical Computer Science (tidsskrift). - 1999. - Bd. 223 . - S. 179-191 . - doi : 10.1016/S0304-3975(98)00120-0 . Arkiveret fra originalen den 12. september 2006.
• Mehta, DP og Sahni, S. 32. PQ-træer, pc-træer og plane grafer // Håndbog i datastrukturer og applikationer. — Taylor & Francis, 2004. — ISBN 9781420035179 .
• 3.2. Planaritetstest // Planar Graphs: Theory and Algorithms / red. af T. Nishizeki og N. Chiba. - Nord-Holland, 1988. - ISBN 0-444-702121 .