1053:
what the mapping IS. Only the purpose the mapping. Ok, ok, I get it, it's used to speed up things. But what IS it? What IS the mapping? Then if I read the definition section, it says "Intuitively, a tree decomposition represents the vertices of the given graph as subtrees of a tree, in such a way that vertices are adjacent only when the corresponding subtrees intersect." But this is confusing in the following ways: (1) I do not know what it means to represent vertices of a graph as subtrees. Vertices are vertices; a tree has vertices AND edges. So this sentence does not type-check for me. Do you really mean a subgraph of this graph is represented as subtrees? (2) It is getting ambiguous when specifying "vertices are adjacent" ... vertices of WHAT are adjacent? The original graph? The tree decomposition? This whole introduction really needs to be rewritten... I cannot understand it, and I'm a PhD in computer science. --
1088:
computed using "nice" tree decompositions (i.e. with leaf, forget, introduce, join nodes) and a convincing sketch proof of correctness fits into a few lines. Of course you need to leverage the known result that nice tree decompositions do not inflate the width of the decomposition, but I'd consider this a small price to pay for explaining to a wider audience the power of DP on tree decompositions. So I guess the question is: is it a good idea to introduce nice tree decompositions and give a (sketch) proof of why the DP is correct?
84:
74:
53:
256:
179:
158:
22:
875:
1027:
Following , "Junction Tree" is a tree-decomposition into complete parts (ie, each bag is a clique). Such decomposition is possible iff graph is triangulated. For relevance to inference -- in an undirected graphical model, conditioning on a separator of the graph makes separated parts of probabilistic
1052:
The wording of the intro to this article could be improved: I just read it and yet cannot figure out what a Tree
Decomposition IS. The intro says "a tree decomposition is a mapping of a graph into a tree that can be used to speed up solving certain problems on the original graph." but does not say
928:
The article claims "A graph has treewidth 1 if and only if it is a tree", which is not true: forests consisting of multiple trees have treewidth at most 1, too, and trees (forests) without edges have treewidth 0. I'm not sure how to best correct this though, as I'm reluctant to change the section
522:
I think they are the same, and merged them. There was a very vague handwavy description of how to find a tree decomposition in the junction tree article, which I didn't consider worth saving, but there's plenty more that could be said in this article on the topic of decomposition algorithms. This
1087:
When I was first learning dynamic programming on tree decompositions I found the
Independent Set example currently on the Tree Decomposition page (with a recurrence for both A and B) really quite dense and confusing. On the other hand, there are slides on the internet in which Vertex Cover is
277:
557:
I agree - they are not the same. The junction tree is one particular tree decomposition, it is the one which maximizes the weight of the tree. The weight of tree is the sum of its edge weights. The weight of an edge is the number of nodes shared by the two cliques it connects.
634:
1032:. Conditioning on separators in Bayesian networks does not always create independent subproblems, but every Bayesian network can be converted to an undirected graphical model (this involves moralizing the graph).
301:
140:
441:
358:
296:
870:{\displaystyle A(S,i)=|S|+\sum _{j\in C(i)}\left((\max _{S'\subset X_{j} \atop {S\cap X_{j}=S'\cap X_{i} \atop S\cup S'{\text{independent set}}}}A(S',j))-|S\cap X_{j}|\right)}
1126:
229:
219:
606:
1131:
626:
534:
I don't believe that they are the same- I believe a junction tree is a specific type of join tree, which is optimised for the calculation of bayesian inference.
195:
1121:
1116:
403:
130:
377:
242:
186:
163:
106:
1111:
466:
559:
909:
541:
349:
930:
985:
330:
97:
58:
422:
902:
Could anyone provide a reference for a really good book covering this and similar (algorithms and graph theory) topics?
387:
268:
33:
397:
311:
432:
194:
related articles on
Knowledge. If you would like to participate, please visit the project page, where you can join
1028:
network independent, so inference can proceed recursively using tree decomposition, this algorithm is called the
459:
1037:
1016:
949:
563:
913:
545:
1029:
969:
965:
934:
1093:
1033:
989:
1008:
368:
39:
83:
1089:
905:
537:
21:
1012:
945:
524:
105:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
89:
73:
52:
881:
579:
I have a suggestion for a different formulation of A in the recursion for
Independent Set. Let
287:
1058:
1004:
339:
191:
582:
1072:
885:
413:
255:
611:
278:
Requested articles/Applied arts and sciences/Computer science, computing, and
Internet
1105:
977:
973:
505:
628:
in the tree decomposition. (Since we have chosen a root for the tree this is ok.)
1054:
1000:
102:
79:
1097:
1076:
1062:
1041:
1020:
993:
953:
938:
917:
889:
567:
549:
527:
516:
513:
509:
320:
1069:
178:
157:
980:
is a redirect back to this here article. So, what a junction tree
880:
This way we dont need the extra function B. What do you think?
396:
Find pictures for the biographies of computer scientists (see
15:
964:
in the article, the link "junction tree" actually links to
1011:, but I'm not certain enough to make that change here. —
637:
614:
585:
972:
again has a link to junction tree. This one goes to
929:
from "treewidth of trees" to "treewidth of forests".
190:, a collaborative effort to improve the coverage of
101:, a collaborative effort to improve the coverage of
869:
620:
600:
302:Computer science articles needing expert attention
709:
1068:Agree, the wording is still less than optimal.
944:I changed it to talk about connected graphs. —
523:should link in to graph separators, as well. —
442:WikiProject Computer science/Unreferenced BLPs
8:
359:Computer science articles without infoboxes
297:Computer science articles needing attention
263:Here are some tasks awaiting attention:
237:
152:
47:
999:I think it's a tree decomposition of the
857:
851:
836:
796:
774:
750:
737:
730:
712:
679:
667:
659:
636:
613:
584:
1127:Mid-importance Computer science articles
154:
49:
19:
204:Knowledge:WikiProject Computer science
1132:WikiProject Computer science articles
504:What's the relation between this and
207:Template:WikiProject Computer science
7:
184:This article is within the scope of
95:This article is within the scope of
38:It is of interest to the following
738:
713:
378:Timeline of computing 2020–present
14:
1122:B-Class Computer science articles
1117:Mid-priority mathematics articles
575:The recursion for Independent Set
404:Computing articles needing images
115:Knowledge:WikiProject Mathematics
254:
177:
156:
118:Template:WikiProject Mathematics
82:
72:
51:
20:
608:be the direct children of node
224:This article has been rated as
135:This article has been rated as
858:
837:
830:
827:
810:
705:
695:
689:
668:
660:
653:
641:
595:
589:
1:
458:Tag all relevant articles in
198:and see a list of open tasks.
109:and see a list of open tasks.
1112:B-Class mathematics articles
1077:13:28, 5 February 2013 (UTC)
1063:22:23, 9 February 2012 (UTC)
1042:23:51, 6 November 2010 (UTC)
1021:02:06, 15 January 2010 (UTC)
994:02:01, 15 January 2010 (UTC)
890:10:37, 7 December 2007 (UTC)
550:09:30, 21 October 2008 (UTC)
528:16:30, 3 November 2007 (UTC)
467:WikiProject Computer science
243:WikiProject Computer science
187:WikiProject Computer science
1098:11:48, 18 August 2015 (UTC)
1003:of the representation of a
918:19:42, 8 January 2008 (UTC)
398:List of computer scientists
1148:
954:00:52, 1 August 2008 (UTC)
517:03:13, 20 March 2007 (UTC)
500:Relation to junction trees
230:project's importance scale
939:17:09, 31 July 2008 (UTC)
568:14:41, 27 June 2009 (UTC)
460:Category:Computer science
236:
223:
210:Computer science articles
172:
134:
67:
46:
1083:Nice tree decompositions
462:and sub-categories with
141:project's priority scale
1030:junction tree algorithm
970:junction tree algorithm
966:junction tree algorithm
98:WikiProject Mathematics
1009:directed acyclic graph
871:
622:
602:
423:Computer science stubs
28:This article is rated
872:
623:
603:
512:? Are they the same?
635:
612:
601:{\displaystyle C(i)}
583:
241:Things you can help
121:mathematics articles
984:remains unclear. --
924:Treewidth of trees
867:
806:
699:
618:
598:
90:Mathematics portal
34:content assessment
920:
908:comment added by
804:
802:
799:
708:
675:
621:{\displaystyle i}
570:Dmitry Kamenetsky
540:comment added by
497:
496:
493:
492:
489:
488:
485:
484:
481:
480:
151:
150:
147:
146:
1139:
1034:Yaroslav Bulatov
1005:Bayesian network
903:
876:
874:
873:
868:
866:
862:
861:
856:
855:
840:
820:
805:
803:
801:
800:
797:
795:
780:
779:
778:
766:
755:
754:
736:
735:
734:
722:
698:
671:
663:
627:
625:
624:
619:
607:
605:
604:
599:
552:
471:
465:
340:Computer science
269:Article requests
258:
251:
250:
238:
212:
211:
208:
205:
202:
201:Computer science
192:Computer science
181:
174:
173:
168:
164:Computer science
160:
153:
123:
122:
119:
116:
113:
92:
87:
86:
76:
69:
68:
63:
55:
48:
31:
25:
24:
16:
1147:
1146:
1142:
1141:
1140:
1138:
1137:
1136:
1102:
1101:
1085:
1050:
1048:Wording of lead
962:
926:
900:
847:
813:
798:independent set
788:
781:
770:
759:
746:
739:
726:
715:
714:
704:
700:
633:
632:
610:
609:
581:
580:
577:
535:
502:
477:
474:
469:
463:
451:Project-related
446:
427:
408:
382:
363:
344:
325:
306:
282:
209:
206:
203:
200:
199:
166:
120:
117:
114:
111:
110:
88:
81:
61:
32:on Knowledge's
29:
12:
11:
5:
1145:
1143:
1135:
1134:
1129:
1124:
1119:
1114:
1104:
1103:
1084:
1081:
1080:
1079:
1049:
1046:
1045:
1044:
1024:
1023:
1013:David Eppstein
961:
958:
957:
956:
946:David Eppstein
925:
922:
899:
896:
894:
878:
877:
865:
860:
854:
850:
846:
843:
839:
835:
832:
829:
826:
823:
819:
816:
812:
809:
794:
791:
787:
784:
777:
773:
769:
765:
762:
758:
753:
749:
745:
742:
733:
729:
725:
721:
718:
711:
707:
703:
697:
694:
691:
688:
685:
682:
678:
674:
670:
666:
662:
658:
655:
652:
649:
646:
643:
640:
617:
597:
594:
591:
588:
576:
573:
572:
571:
560:115.129.16.201
554:
553:
531:
530:
525:David Eppstein
501:
498:
495:
494:
491:
490:
487:
486:
483:
482:
479:
478:
476:
475:
473:
472:
455:
447:
445:
444:
438:
428:
426:
425:
419:
409:
407:
406:
401:
393:
383:
381:
380:
374:
364:
362:
361:
355:
345:
343:
342:
336:
326:
324:
323:
317:
307:
305:
304:
299:
293:
283:
281:
280:
274:
262:
260:
259:
247:
246:
234:
233:
226:Mid-importance
222:
216:
215:
213:
196:the discussion
182:
170:
169:
167:Mid‑importance
161:
149:
148:
145:
144:
133:
127:
126:
124:
107:the discussion
94:
93:
77:
65:
64:
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
1144:
1133:
1130:
1128:
1125:
1123:
1120:
1118:
1115:
1113:
1110:
1109:
1107:
1100:
1099:
1095:
1091:
1082:
1078:
1074:
1070:
1067:
1066:
1065:
1064:
1060:
1056:
1047:
1043:
1039:
1035:
1031:
1026:
1025:
1022:
1018:
1014:
1010:
1006:
1002:
998:
997:
996:
995:
991:
987:
983:
979:
978:junction tree
975:
974:junction tree
971:
967:
960:junction tree
959:
955:
951:
947:
943:
942:
941:
940:
936:
932:
923:
921:
919:
915:
911:
910:81.110.32.149
907:
897:
895:
892:
891:
887:
883:
863:
852:
848:
844:
841:
833:
824:
821:
817:
814:
807:
792:
789:
785:
782:
775:
771:
767:
763:
760:
756:
751:
747:
743:
740:
731:
727:
723:
719:
716:
701:
692:
686:
683:
680:
676:
672:
664:
656:
650:
647:
644:
638:
631:
630:
629:
615:
592:
586:
574:
569:
565:
561:
556:
555:
551:
547:
543:
542:129.215.90.27
539:
533:
532:
529:
526:
521:
520:
519:
518:
515:
511:
507:
506:Junction tree
499:
468:
461:
457:
456:
454:
452:
448:
443:
440:
439:
437:
435:
434:
429:
424:
421:
420:
418:
416:
415:
410:
405:
402:
399:
395:
394:
392:
390:
389:
384:
379:
376:
375:
373:
371:
370:
365:
360:
357:
356:
354:
352:
351:
346:
341:
338:
337:
335:
333:
332:
327:
322:
319:
318:
316:
314:
313:
308:
303:
300:
298:
295:
294:
292:
290:
289:
284:
279:
276:
275:
273:
271:
270:
265:
264:
261:
257:
253:
252:
249:
248:
244:
240:
239:
235:
231:
227:
221:
218:
217:
214:
197:
193:
189:
188:
183:
180:
176:
175:
171:
165:
162:
159:
155:
142:
138:
132:
129:
128:
125:
108:
104:
100:
99:
91:
85:
80:
78:
75:
71:
70:
66:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
1086:
1051:
981:
963:
931:85.178.88.61
927:
901:
893:
879:
578:
503:
450:
449:
433:Unreferenced
431:
430:
412:
411:
386:
385:
367:
366:
348:
347:
329:
328:
310:
309:
286:
285:
267:
266:
225:
185:
137:Mid-priority
136:
96:
62:Mid‑priority
40:WikiProjects
1090:Steven.kelk
1001:moral graph
986:91.0.23.173
904:—Preceding
882:Dag Hovland
536:—Preceding
112:Mathematics
103:mathematics
59:Mathematics
1106:Categories
510:join tree
321:Computing
906:unsigned
538:unsigned
369:Maintain
312:Copyedit
350:Infobox
288:Cleanup
228:on the
139:on the
30:B-class
1055:Toomim
976:. But
898:Books?
331:Expand
36:scale.
1007:as a
414:Stubs
388:Photo
245:with:
1094:talk
1073:talk
1059:talk
1038:talk
1017:talk
990:talk
950:talk
935:talk
914:talk
886:talk
564:talk
546:talk
514:Took
710:max
508:or
220:Mid
131:Mid
1108::
1096:)
1075:)
1061:)
1040:)
1019:)
992:)
982:is
968:.
952:)
937:)
916:)
888:)
845:∩
834:−
786:∪
768:∩
744:∩
724:⊂
684:∈
677:∑
566:)
548:)
470:}}
464:{{
1092:(
1071:(
1057:(
1036:(
1015:(
988:(
948:(
933:(
912:(
884:(
864:)
859:|
853:j
849:X
842:S
838:|
831:)
828:)
825:j
822:,
818:′
815:S
811:(
808:A
793:′
790:S
783:S
776:i
772:X
764:′
761:S
757:=
752:j
748:X
741:S
732:j
728:X
720:′
717:S
706:(
702:(
696:)
693:i
690:(
687:C
681:j
673:+
669:|
665:S
661:|
657:=
654:)
651:i
648:,
645:S
642:(
639:A
616:i
596:)
593:i
590:(
587:C
562:(
544:(
453::
436::
417::
400:)
391::
372::
353::
334::
315::
291::
272::
232:.
143:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
