PQ fa

A PQ fa  egy adatstruktúra egy permutációs csoport megjelenítésére . Ez egy gyökeres sík fa . A benne lévő lógó csúcsok permutálható elemeket képviselnek. A többi csúcs vagy , vagy feliratú . A megjelölt csúcsoknak legalább 3, a megjelölt csúcsoknak pedig legalább 2 gyermekük van. A PQ-fában megengedett a tetszőlegesen megjelölt csúcs leszármazottainak átrendezése és a megjelölt csúcs leszármazottainak sorrendjének megfordítása .

A PQ-fák olyan permutációk keresésére szolgálnak, amelyek korlátozásai fokozatosan, egyenként ismertek. Ilyen problémák merülnek fel a DNS újraalkotásakor és a gráf síkságának ellenőrzésekor.

Cikkek

• Booth, Kellogg S. és Lueker, George S. Testing for the consecutive one property, interval graphs and graph planarity using PQ-tree algoritms  //  Journal of Computer and System Sciences. - 1976. - 1. évf. 13 , sz. 3 . — P. 335–379 . - doi : 10.1016/S0022-0000(76)80045-1 .
• Shih, Wei-Kuan és Hsu, Wen-Lian. Új síksági teszt  (angol)  // Theoretical Computer Science (folyóirat). - 1999. - 1. évf. 223 . - P. 179-191 . - doi : 10.1016/S0304-3975(98)00120-0 . Az eredetiből archiválva: 2006. szeptember 12.
• Mehta, DP and Sahni, S. 32. PQ Trees, PC Trees, and Planar Graphs // Handbook of Data Structures and Applications. — Taylor és Francis, 2004. — ISBN 9781420035179 .
• 3.2. Síksági vizsgálat // Planar Graphs: Theory and Algorithms / szerk. T. Nishizeki és N. Chiba. - Észak-Hollandia, 1988. - ISBN 0-444-702121 .