PQ puu

PQ-puu  on tietorakenne permutaatioryhmän esittämiseksi . Tämä on juurtunut tasomainen puu . Sen roikkuvat kärjet edustavat muuttuvia elementtejä. Loput kärjet on merkitty joko , tai . Merkityillä pisteillä on vähintään 3 lasta ja merkityillä pisteillä vähintään 2 lasta. PQ-puussa on sallittua järjestää mielivaltaisesti merkityn kärjen jälkeläiset ja kääntää merkityn kärjen jälkeläisten järjestys päinvastaiseksi .

PQ-puiden avulla etsitään permutaatioita, joiden rajoitukset tunnetaan asteittain, yksitellen. Tällaisia ​​ongelmia syntyy, kun DNA:ta luodaan uudelleen ja graafin tasomaisuutta tarkistetaan.

Artikkelit

• Booth, Kellogg S. ja Lueker, George S. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algoritms  //  Journal of Computer and System Sciences. - 1976. - Voi. 13 , ei. 3 . — s. 335–379 . - doi : 10.1016/S0022-0000(76)80045-1 .
• Shih, Wei-Kuan ja Hsu, Wen-Lian. Uusi tasomaisuustesti  (englanniksi)  // Teoreettinen tietojenkäsittelytiede (lehti). - 1999. - Voi. 223 . - s. 179-191 . - doi : 10.1016/S0304-3975(98)00120-0 . Arkistoitu alkuperäisestä 12. syyskuuta 2006.
• Mehta, DP ja Sahni, S. 32. PQ Trees, PC Trees, and Planar Graphs // Tietorakenteiden ja sovellusten käsikirja. — Taylor & Francis, 2004. — ISBN 9781420035179 .
• 3.2. Tasoisuustestaus // Planar Graphs: Theory and Algorithms / toim. T. Nishizeki ja N. Chiba. - Pohjois-Hollanti, 1988. - ISBN 0-444-702121 .