PQ-дерево

PQ-дерево — структура даних для подання групи перестановок, кореневе планарне дерево. Висячі вершини в ньому відповідають подаваним елементам. Решта вершин мають позначку або . Вершини з позначкою мають принаймні 3 нащадки, а вершини з позначкою мають принаймні 2 нащадки. У PQ-дереві дозволяється як завгодно переставляти нащадків вершини з позначкою і обертати порядок нащадків вершини з позначкою .

PQ-дерево, яке описує вкладений список [1 (2 3 4) 5]
Граф (a) і його PQ-дерево (b)

PQ-дерева використовують для пошуку перестановок, обмеження на які стають відомими поступово, одне за іншим. Такі задачі виникають при відтворенні ДНК і перевірці планарності графу.

Статті
  • Booth, Kellogg S. and Lueker, George S. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms // Journal of Computer and System Sciences. — 1976. — Vol. 13, no. 3 (3 November). — P. 335–379. — DOI:10.1016/S0022-0000(76)80045-1.
  • Shih, Wei-Kuan and Hsu, Wen-Lian. A new planarity test // Theoretical Computer Science (journal). — 1999. — Vol. 223 (3 November). — P. 179–191. — DOI:10.1016/S0304-3975(98)00120-0. Архівовано з джерела 12 вересня 2006.
  • Mehta, D.P. and Sahni, S. 32. PQ Trees, PC Trees, and Planar Graphs // Handbook of Data Structures and Applications. — Taylor & Francis, 2004. — ISBN 9781420035179.
  • 3.2. Planarity testing // Planar Graphs: Theory and Algorithms / ed. by T. Nishizeki and N. Chiba. — North-Holland, 1988. — ISBN 0-444-702121.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.