77:
115:, is a more recent generalization of the PQ tree. Like the PQ tree, it represents permutations by reorderings of nodes in a tree, with elements represented at the leaves of the tree. Unlike the PQ tree, the PC tree is unrooted. The nodes adjacent to any non-leaf node labeled P may be reordered arbitrarily as in the PQ tree, while the nodes adjacent to any non-leaf node labeled C have a fixed
48:
achieved by any sequence of these two operations. A PQ tree with many P and Q nodes can represent complicated subsets of the set of all possible orderings. However, not every set of orderings may be representable in this way; for instance, if an ordering is represented by a PQ tree, the reverse of the ordering must also be represented by the same tree.
89:
Where graphical presentation is unavailable PQ trees are often noted using nested parenthesized lists. Each matched pair of square parentheses represents a Q node and each matched pair of rounded parentheses represent a P node. Leaves are non-parentheses elements of the lists. The image on the
85:
If all the leaves of a PQ tree are connected directly to a root P node then all possible orderings are allowed. If all the leaves are connected directly to a root Q node then only one order and its reverse are allowed. If nodes a,b,c connect to a P node, which connects to a root P node, with all
47:
A PQ tree represents its permutations via permissible reorderings of the children of its nodes. The children of a P node may be reordered in any way. The children of a Q node may be put in reverse order, but may not otherwise be reordered. A PQ tree represents all leaf node orderings that can be
51:
PQ trees are used to solve problems where the goal is to find an ordering that satisfies various constraints. In these problems, constraints on the ordering are included one at a time, by modifying the PQ tree structure in such a way that it represents only orderings satisfying the constraint.
119:
and may only be reordered by reversing this order. Thus, a PC tree can only represent sets of orderings in which any circular permutation or reversal of an ordering in the set is also in the set. However, a PQ tree on
170:
244:
557:
764:
308:
820:
211:
424:
90:
left is represented in this notation by . This PQ tree represents the following twelve permutations on the set {1, 2, 3, 4, 5}:
141:
128:+ 1 elements, where the extra element serves to root the PC tree. The data structure operations required to perform a
389:
774:
236:
213:
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of
Computing, May 16-18, 1993, San Diego, CA, USA
330:
301:
166:"Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms"
86:
other leaf nodes connected directly to the root, then any ordering where a,b,c are contiguous is allowed.
468:
317:
33:
29:
458:
413:
572:
348:
108:
428:
112:
44:
is labelled P or Q. A P node has at least two children, and a Q node has at least three children.
739:
698:
524:
514:
393:
633:
334:
294:
129:
724:
253:
217:
207:
179:
202:(1993). "Mapping the genome: some combinatorial problems arising in molecular biology". In
668:
418:
203:
199:
132:
algorithm on PC trees are somewhat simpler than the corresponding operations on PQ trees.
36:
in 1976. It is a rooted, labeled tree, in which each element is represented by one of the
281:
621:
616:
499:
433:
61:
21:
276:
258:
184:
165:
814:
769:
749:
592:
481:
408:
41:
343:
729:
693:
509:
504:
486:
398:
116:
94:
12345, 12435, 13245, 13425, 14235, 14325, 52341, 52431, 53241, 53421, 54231, 54321.
65:
779:
744:
734:
648:
582:
577:
567:
476:
325:
25:
76:
789:
759:
719:
562:
491:
438:
358:
794:
754:
601:
529:
519:
37:
60:
fragments, testing a matrix for the consecutive ones property, recognizing
683:
373:
221:
799:
673:
653:
626:
611:
363:
688:
663:
606:
453:
383:
378:
353:
286:
703:
678:
658:
643:
552:
443:
368:
53:
547:
448:
403:
75:
539:
290:
57:
216:. Association for Computing Machinery. pp. 278–285.
712:
591:
538:
467:
324:
277:PQ Tree Algorithm and Consecutive Ones Problem
28:on a set of elements, discovered and named by
302:
164:Booth, Kellogg S.; Lueker, George S. (1976).
8:
52:Applications of PQ trees include creating a
309:
295:
287:
124:elements may be simulated by a PC tree on
257:
183:
171:Journal of Computer and System Sciences
153:
235:Shih, Wei-Kuan; Hsu, Wen-Lian (1999).
159:
157:
64:, and determining whether a graph is
7:
14:
1:
259:10.1016/S0304-3975(98)00120-0
185:10.1016/S0022-0000(76)80045-1
142:Series-parallel partial order
245:Theoretical Computer Science
24:that represents a family of
282:Javascript demo of PQ Trees
837:
80:The PQ tree representing
210:; Aggarwal, Alok (eds.).
765:Left-child right-sibling
821:Trees (data structures)
595:data partitioning trees
553:C-trie (compressed ADT)
237:"A new planarity test"
82:
222:10.1145/167088.167170
79:
72:Examples and notation
775:Log-structured merge
318:Tree data structures
740:Fractal tree index
335:associative arrays
83:
808:
807:
208:Johnson, David S.
130:planarity testing
828:
311:
304:
297:
288:
264:
263:
261:
252:(1–2): 179–191.
241:
232:
226:
225:
204:Kosaraju, S. Rao
200:Karp, Richard M.
196:
190:
189:
187:
161:
34:George S. Lueker
30:Kellogg S. Booth
20:is a tree-based
836:
835:
831:
830:
829:
827:
826:
825:
811:
810:
809:
804:
708:
587:
534:
463:
459:Weight-balanced
414:Order statistic
328:
320:
315:
273:
268:
267:
239:
234:
233:
229:
198:
197:
193:
163:
162:
155:
150:
138:
107:, developed by
101:
81:
74:
62:interval graphs
12:
11:
5:
834:
832:
824:
823:
813:
812:
806:
805:
803:
802:
797:
792:
787:
782:
777:
772:
767:
762:
757:
752:
747:
742:
737:
732:
727:
722:
716:
714:
710:
709:
707:
706:
701:
696:
691:
686:
681:
676:
671:
666:
661:
656:
651:
646:
641:
624:
619:
614:
609:
604:
598:
596:
589:
588:
586:
585:
580:
575:
573:Ternary search
570:
565:
560:
555:
550:
544:
542:
536:
535:
533:
532:
527:
522:
517:
512:
507:
502:
497:
489:
484:
479:
473:
471:
465:
464:
462:
461:
456:
451:
446:
441:
436:
431:
421:
416:
411:
406:
401:
396:
386:
381:
376:
371:
366:
361:
356:
351:
346:
340:
338:
322:
321:
316:
314:
313:
306:
299:
291:
285:
284:
279:
272:
271:External links
269:
266:
265:
227:
191:
178:(3): 335–379.
152:
151:
149:
146:
145:
144:
137:
134:
100:
97:
96:
95:
73:
70:
22:data structure
13:
10:
9:
6:
4:
3:
2:
833:
822:
819:
818:
816:
801:
798:
796:
793:
791:
788:
786:
783:
781:
778:
776:
773:
771:
768:
766:
763:
761:
758:
756:
753:
751:
750:Hash calendar
748:
746:
743:
741:
738:
736:
733:
731:
728:
726:
723:
721:
718:
717:
715:
711:
705:
702:
700:
697:
695:
692:
690:
687:
685:
682:
680:
677:
675:
672:
670:
667:
665:
662:
660:
657:
655:
652:
650:
647:
645:
642:
639:
637:
631:
629:
625:
623:
620:
618:
615:
613:
610:
608:
605:
603:
600:
599:
597:
594:
590:
584:
581:
579:
576:
574:
571:
569:
566:
564:
561:
559:
556:
554:
551:
549:
546:
545:
543:
541:
537:
531:
528:
526:
525:van Emde Boas
523:
521:
518:
516:
515:Skew binomial
513:
511:
508:
506:
503:
501:
498:
496:
494:
490:
488:
485:
483:
480:
478:
475:
474:
472:
470:
466:
460:
457:
455:
452:
450:
447:
445:
442:
440:
437:
435:
432:
430:
426:
422:
420:
417:
415:
412:
410:
407:
405:
402:
400:
397:
395:
394:Binary search
391:
387:
385:
382:
380:
377:
375:
372:
370:
367:
365:
362:
360:
357:
355:
352:
350:
347:
345:
342:
341:
339:
336:
332:
327:
323:
319:
312:
307:
305:
300:
298:
293:
292:
289:
283:
280:
278:
275:
274:
270:
260:
255:
251:
247:
246:
238:
231:
228:
223:
219:
215:
214:
209:
205:
201:
195:
192:
186:
181:
177:
173:
172:
167:
160:
158:
154:
147:
143:
140:
139:
135:
133:
131:
127:
123:
118:
114:
110:
109:Wei-Kuan Shih
106:
98:
93:
92:
91:
87:
78:
71:
69:
67:
63:
59:
55:
49:
45:
43:
42:non-leaf node
39:
35:
31:
27:
23:
19:
784:
635:
627:
492:
425:Left-leaning
331:dynamic sets
326:Search trees
249:
243:
230:
212:
194:
175:
169:
125:
121:
117:cyclic order
113:Wen-Lian Hsu
104:
102:
88:
84:
50:
46:
26:permutations
17:
15:
725:Exponential
713:Other trees
40:, and each
669:Priority R
419:Palindrome
148:References
54:contig map
38:leaf nodes
755:iDistance
634:implicit
622:Hilbert R
617:Cartesian
500:Fibonacci
434:Scapegoat
429:Red–black
815:Category
770:Link/cut
482:Binomial
409:Interval
136:See also
99:PC trees
730:Fenwick
694:Segment
593:Spatial
510:Pairing
505:Leftist
427:)
399:Dancing
392:)
390:Optimal
105:PC tree
18:PQ tree
780:Merkle
745:Fusion
735:Finger
659:Octree
649:Metric
583:Y-fast
578:X-fast
568:Suffix
487:Brodal
477:Binary
66:planar
790:Range
760:K-ary
720:Cover
563:Radix
548:Ctrie
540:Tries
469:Heaps
449:Treap
439:Splay
404:HTree
359:(a,b)
349:2–3–4
240:(PDF)
56:from
795:SPQR
674:Quad
602:Ball
558:Hash
530:Weak
520:Skew
495:-ary
111:and
103:The
32:and
800:Top
654:MVP
612:BSP
364:AVL
344:2–3
254:doi
250:223
218:doi
180:doi
58:DNA
817::
785:PQ
699:VP
689:R*
684:R+
664:PH
638:-d
630:-d
607:BK
454:UB
379:B*
374:B+
354:AA
248:.
242:.
206:;
176:13
174:.
168:.
156:^
68:.
16:A
704:X
679:R
644:M
640:)
636:k
632:(
628:k
493:d
444:T
423:(
388:(
384:B
369:B
337:)
333:/
329:(
310:e
303:t
296:v
262:.
256::
224:.
220::
188:.
182::
126:n
122:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
