{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,29]],"date-time":"2026-08-29T09:55:42Z","timestamp":1787997342540,"version":"build-2784847793"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>Chordal graphs have been extensively studied and have applications in various fields, including computational biology, sparse matrix computation, and graphical models. They are characterized by the existence of clique trees, whose vertices correspond to the maximal cliques of a chordal graph. In many applications, it is the clique tree of the chordal graph that is of greatest utility. In general, the number of clique trees can grow exponentially with the size of the chordal graph, and in some applications, particular clique trees have greater utility; we want additional criteria to select the most useful clique tree(s). A natural criterion in phylogenetics (and perhaps elsewhere) is that of compactness. In this paper, we formalize this criterion as the average distance between nodes, and present a characterization of clique trees that satisfies this criterion. We also develop a polynomial-time algorithm to find such a clique tree, and show that any minimum average-distance clique tree of a chordal graph can be constructed by our algorithm.<\/jats:p>","DOI":"10.1137\/15m1021052","type":"journal-article","created":{"date-parts":[[2015,9,15]],"date-time":"2015-09-15T11:23:45Z","timestamp":1442316225000},"page":"1706-1734","source":"Crossref","is-referenced-by-count":3,"title":["Minimum Average Distance Clique Trees"],"prefix":"10.1137","volume":"29","author":[{"given":"Shou-Jun","family":"Xu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rob","family":"Gysel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dan","family":"Gusfield","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,9,15]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-010-5233-4"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/0210059"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.07.001"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.09.059"},{"key":"atypb5","first-page":"1","author":"Blair J. R. S.","year":"1993","journal-title":"New York"},{"key":"atypb6","first-page":"173","volume":"1","author":"Blair J. R. S.","year":"1994","journal-title":"Nordic J. Comput."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.06.015"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.02.013"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(74)90002-8"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"A. Darwiche,\n                      Modeling and Reasoning with Bayesian Networks\n                      , Cambridge University Press, New York, 2009.","DOI":"10.1017\/CBO9780511811357"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02992776"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010767517079"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016290123303"},{"key":"atypb14","doi-asserted-by":"crossref","first-page":"283","DOI":"10.21136\/CMJ.1976.101401","volume":"26","author":"Entringer R. C.","year":"1976","journal-title":"Czechoslovak Math. J."},{"key":"atypb15","first-page":"203","author":"D","year":"2001","journal-title":"The Netherlands"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1965.15.835"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90094-X"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90053-8"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"M. C. Golumbic,\n                      Algorithmic Graph Theory and Perfect Graphs\n                      , Ann. Discrete Math. 57, Elsevier Science, Amsterdam, 2004.","DOI":"10.1016\/S0167-5060(04)80051-7"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2009.0200"},{"key":"atypb21","unstructured":"D. L. Hartl,\n                      A Primer of Population Genetics\n                      , 3rd ed., Sinauer, Sunderland, MA, 2000."},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90178-0"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90070-7"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/090776305"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)90511-Q"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.7151\/dmgt.1061"},{"key":"atypb27","first-page":"304","author":"Meacham C. A.","year":"1983","journal-title":"Berlin"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230080402"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"J. Pearl,\n                      Probabilistic reasoning in intelligent systems: Networks of plausible inference\n                      , Morgan Kaufman, San Francisco, 1988.","DOI":"10.1016\/B978-0-08-051489-5.50008-4"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(70)90282-9"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(01)00174-1"},{"key":"atypb32","unstructured":"C. Semple and M. Steel,\n                      Phylogenetics\n                      , Oxford Lecture Ser. Math. Appl. 24, J. Ball and D. Welsh, eds., Oxford University Press, Oxford, 2003."},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1007\/BF02618470"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1561\/2400000006"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190020311"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1021\/ja01193a005"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M1021052","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:18:14Z","timestamp":1787318294000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M1021052"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/15M1021052"],"URL":"https:\/\/doi.org\/10.1137\/15m1021052","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}