{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:44:24Z","timestamp":1759063464573},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2011,11,22]],"date-time":"2011-11-22T00:00:00Z","timestamp":1321920000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"},{"start":{"date-parts":[[2011,11,22]],"date-time":"2011-11-22T00:00:00Z","timestamp":1321920000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Braz Comput Soc"],"published-print":{"date-parts":[[2012,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Chordal graphs have characteristic tree representations, the clique trees. The problems of finding one or enumerating them have already been solved in a satisfactory way. In this paper, the following related problem is studied: given a family \"Equation missing\"<!-- image only, no MathML or LaTex --> of trees, all having the same vertex set <jats:italic>V<\/jats:italic>, determine whether there exists a chordal graph whose set of clique trees equals \"Equation missing\"<!-- image only, no MathML or LaTex -->. For that purpose, we undertake a study of the structural properties, some already known and some new, of the clique trees of a chordal graph and the characteristics of the sets that induce subtrees of every clique tree. Some necessary and sufficient conditions and examples of how they can be applied are found, eventually establishing that a positive or negative answer to the problem can be obtained in polynomial time. If affirmative, a graph whose set of clique trees equals \"Equation missing\"<!-- image only, no MathML or LaTex --> is also obtained. Finally, all the chordal graphs with set of clique trees equal to \"Equation missing\"<!-- image only, no MathML or LaTex --> are characterized.<\/jats:p>","DOI":"10.1007\/s13173-011-0048-0","type":"journal-article","created":{"date-parts":[[2011,11,21]],"date-time":"2011-11-21T15:31:39Z","timestamp":1321889499000},"page":"121-128","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Determining what sets of trees can be the clique trees of a chordal graph"],"prefix":"10.1007","volume":"18","author":[{"given":"Pablo","family":"De Caria","sequence":"first","affiliation":[]},{"given":"Marisa","family":"Gutierrez","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,11,22]]},"reference":[{"key":"48_CR1","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/j.endm.2011.05.007","volume":"37","author":"P De Caria","year":"2011","unstructured":"De Caria P, Gutierrez M (2011) Comparing trees characteristic to chordal and dually chordal graphs. Electron Notes Discrete Math 37:33\u201338","journal-title":"Electron Notes Discrete Math"},{"key":"48_CR2","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"GA Dirac","year":"1961","unstructured":"Dirac GA (1961) On rigid circuit graphs. Abh Math Semin Univ Hamb 25:71\u201376","journal-title":"Abh Math Semin Univ Hamb"},{"key":"48_CR3","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1007\/3-540-60618-1_88","volume":"1017","author":"P Galinier","year":"1995","unstructured":"Galinier P, Habib M, Paul C (1995) Chordal graphs and their clique graphs. Lect Notes Comput Sci 1017:358\u2013371","journal-title":"Lect Notes Comput Sci"},{"key":"48_CR4","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"116","author":"F Gavril","year":"1974","unstructured":"Gavril F (1974) The intersection graphs of subtrees in trees are exactly the chordal graphs. J Comb Theory, Ser B 116:47\u201356","journal-title":"J Comb Theory, Ser B"},{"key":"48_CR5","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1016\/0196-6774(87)90053-8","volume":"8","author":"F Gavril","year":"1987","unstructured":"Gavril F (1987) Generating the maximum weight spanning trees of a weighted graph. J Algorithms 8:592\u2013597","journal-title":"J Algorithms"},{"key":"48_CR6","series-title":"Annals of discrete mathematics","first-page":"10","volume-title":"Algorithmic graph theory and perfect graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic MC (2004) Algorithmic graph theory and perfect graphs, 2nd edn. Annals of discrete mathematics, vol 57. Elsevier, Amsterdam, p 10","edition":"2"},{"key":"48_CR7","doi-asserted-by":"crossref","unstructured":"Habib H, Stacho J (2011) Reduced clique graphs of chordal graphs. Accepted to Eur J Combin","DOI":"10.1016\/j.ejc.2011.09.031"},{"key":"48_CR8","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"JB Kruskal","year":"1956","unstructured":"Kruskal JB (1956) On the shortest spanning tree of a graph and the traveling salesman problem. Proc Am Math Soc 7:48\u201350","journal-title":"Proc Am Math Soc"},{"key":"48_CR9","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1137\/0210059","volume":"10","author":"PA Bernstein","year":"1981","unstructured":"Bernstein PA, Goodman N (1981) Power of natural semijoins. SIAM J Comput 10:751\u2013771","journal-title":"SIAM J Comput"},{"key":"48_CR10","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1002\/jgt.3190120313","volume":"12","author":"Y Shibata","year":"1988","unstructured":"Shibata Y (1988) On the tree representation of chordal graphs. J\u00a0Graph Theory 12:421\u2013428","journal-title":"J\u00a0Graph Theory"},{"key":"48_CR11","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/S0166-218X(00)00336-X","volume":"117","author":"Kumara P Sreenivasa","year":"2002","unstructured":"Sreenivasa Kumara P, Veni Madhavanb CE (2002) Clique tree generalization and new subclasses of chordal graphs. Discrete Appl Math 117:109\u2013131","journal-title":"Discrete Appl Math"}],"container-title":["Journal of the Brazilian Computer Society"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-011-0048-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13173-011-0048-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-011-0048-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-011-0048-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T17:24:20Z","timestamp":1630517060000},"score":1,"resource":{"primary":{"URL":"https:\/\/journal-bcs.springeropen.com\/articles\/10.1007\/s13173-011-0048-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,11,22]]},"references-count":11,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["48"],"URL":"https:\/\/doi.org\/10.1007\/s13173-011-0048-0","relation":{},"ISSN":["0104-6500","1678-4804"],"issn-type":[{"value":"0104-6500","type":"print"},{"value":"1678-4804","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,11,22]]},"assertion":[{"value":"24 October 2011","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 October 2011","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 November 2011","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}