{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T15:50:59Z","timestamp":1773762659750,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642041273","type":"print"},{"value":"9783642041280","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04128-0_27","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T14:16:36Z","timestamp":1252937796000},"page":"290-300","source":"Crossref","is-referenced-by-count":14,"title":["Polynomial-Time Algorithm for the Leafage of Chordal Graphs"],"prefix":"10.1007","author":[{"given":"Michel","family":"Habib","sequence":"first","affiliation":[]},{"given":"Juraj","family":"Stacho","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"27_CR1","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K.S. Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci.\u00a013, 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"27_CR2","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/s00607-002-1461-1","volume":"69","author":"H. Broersma","year":"2002","unstructured":"Broersma, H., Fomin, F.V., Ne\u0161et\u0159il, J., Woeginger, G.J.: More about subcolorings. Computing\u00a069, 187\u2013203 (2002)","journal-title":"Computing"},{"key":"27_CR3","doi-asserted-by":"publisher","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D.R. Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pacific Journal of Mathematics\u00a015, 835\u2013855 (1965)","journal-title":"Pacific Journal of Mathematics"},{"key":"27_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1007\/3-540-60618-1_88","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"P. Galinier","year":"1995","unstructured":"Galinier, P., Habib, M., Paul, C.: Chordal graphs and their clique graphs. In: Nagl, M. (ed.) WG 1995. LNCS, vol.\u00a01017, pp. 358\u2013371. Springer, Heidelberg (1995)"},{"key":"27_CR5","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F. Gavril","year":"1974","unstructured":"Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. Journal of Combinatorial Theory B\u00a016, 47\u201356 (1974)","journal-title":"Journal of Combinatorial Theory B"},{"key":"27_CR6","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)"},{"key":"27_CR7","doi-asserted-by":"crossref","unstructured":"Habib, M., Stacho, J.: Linear algorithms for chordal graphs of bounded directed vertex leafage. In: DIMAP Workshop on Algorithmic Graph Theory, Electronic Notes in Discrete Mathematics, vol.\u00a032, pp. 99\u2013108 (2009)","DOI":"10.1016\/j.endm.2009.02.014"},{"key":"27_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/BFb0024501","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"T. Kloks","year":"1997","unstructured":"Kloks, T., Kratsch, D., M\u00fcller, H.: Asteroidal sets in graphs. In: M\u00f6hring, R.H. (ed.) WG 1997. LNCS, vol.\u00a01335, pp. 229\u2013241. Springer, Heidelberg (1997)"},{"key":"27_CR9","doi-asserted-by":"publisher","first-page":"23","DOI":"10.7151\/dmgt.1061","volume":"18","author":"I.J. Lin","year":"1998","unstructured":"Lin, I.J., McKee, T.A., West, D.B.: The leafage of a chordal graph. Discussiones Mathematicae Graph Theory\u00a018, 23\u201348 (1998)","journal-title":"Discussiones Mathematicae Graph Theory"},{"key":"27_CR10","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/BF02941616","volume":"62","author":"E. Prisner","year":"1992","unstructured":"Prisner, E.: Representing triangulated graphs in stars. Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg\u00a062, 29\u201341 (1992)","journal-title":"Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg"},{"key":"27_CR11","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.ipl.2004.12.016","volume":"94","author":"M.S. Rahman","year":"2005","unstructured":"Rahman, M.S., Kaykobad, M.: Complexities of some interesting problems on spanning trees. Information Processing Letters\u00a094, 93\u201397 (2005)","journal-title":"Information Processing Letters"},{"key":"27_CR12","series-title":"Lecture Notes in Computer Science","first-page":"520","volume-title":"LATIN 2008: Theoretical Informatics","author":"J. Stacho","year":"2008","unstructured":"Stacho, J.: On 2-subcolourings of chordal graphs. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol.\u00a04957, pp. 520\u2013530. Springer, Heidelberg (2008)"},{"key":"27_CR13","unstructured":"Stacho, J.: Complexity of subcolourings of chordal graphs (manuscript, 2009)"},{"key":"27_CR14","unstructured":"West, D.B.: personal communication (2008)"},{"key":"27_CR15","volume-title":"Introduction to Graph Theory","author":"D.B. West","year":"2001","unstructured":"West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice Hall, Englewood Cliffs (2001)","edition":"2"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04128-0_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,9]],"date-time":"2019-03-09T14:54:27Z","timestamp":1552143267000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04128-0_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642041273","9783642041280"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04128-0_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}