{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T00:01:57Z","timestamp":1768262517494,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540310006","type":"print"},{"value":"9783540314684","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11604686_38","type":"book-chapter","created":{"date-parts":[[2005,12,5]],"date-time":"2005-12-05T15:02:01Z","timestamp":1133794921000},"page":"433-444","source":"Crossref","is-referenced-by-count":16,"title":["Linear-Time Counting Algorithms for Independent Sets in Chordal Graphs"],"prefix":"10.1007","author":[{"given":"Yoshio","family":"Okamoto","sequence":"first","affiliation":[]},{"given":"Takeaki","family":"Uno","sequence":"additional","affiliation":[]},{"given":"Ryuhei","family":"Uehara","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"38_CR1","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1145\/2402.322389","volume":"30","author":"C. Beeri","year":"1983","unstructured":"Beeri, C., Fagin, R., Maier, D., Yannakakis, M.: On the Desirability of Acyclic Database Schemes. Journal of the ACM\u00a030, 479\u2013513 (1983)","journal-title":"Journal of the ACM"},{"key":"38_CR2","series-title":"IMA","first-page":"1","volume-title":"Graph Theory and Sparse Matrix Computation","author":"J.R.S. Blair","year":"1993","unstructured":"Blair, J.R.S., Peyton, B.: An Introduction to Chordal Graphs and Clique Trees. In: George, A., Gilbert, J.R., Liu, J.W.H. (eds.) Graph Theory and Sparse Matrix Computation. IMA, vol.\u00a056, pp. 1\u201329. Springer, Heidelberg (1993)"},{"key":"38_CR3","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM, Philadelphia (1999)"},{"key":"38_CR4","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0012-365X(74)90002-8","volume":"9","author":"P. Buneman","year":"1974","unstructured":"Buneman, P.: A Characterization of Rigid Circuit Graphs. Discrete Mathematics\u00a09, 205\u2013212 (1974)","journal-title":"Discrete Mathematics"},{"key":"38_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1007\/3-540-44679-6_34","volume-title":"Computing and Combinatorics","author":"L.S. Chandran","year":"2001","unstructured":"Chandran, L.S.: A Linear Time Algorithm for Enumerating All the Minimum and Minimal Separators of a Chordal Graph. In: Wang, J. (ed.) COCOON 2001. LNCS, vol.\u00a02108, pp. 308\u2013317. Springer, Heidelberg (2001)"},{"key":"38_CR6","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/S0304-3975(03)00221-4","volume":"307","author":"L.S. Chandran","year":"2003","unstructured":"Chandran, L.S., Ibarra, L., Ruskey, F., Sawada, J.: Generating and Characterizing the Perfect Elimination Orderings of a Chordal Graph. Theoretical Computer Science\u00a0307, 303\u2013317 (2003)","journal-title":"Theoretical Computer Science"},{"key":"38_CR7","first-page":"451","volume-title":"Proc. 16th Ann. ACM-SIAM Symp. on Discrete Algorithms","author":"D. Eppstein","year":"2005","unstructured":"Eppstein, D.: All Maximal Independent Sets and Dynamic Dominance for Sparse Graphs. In: Proc. 16th Ann. ACM-SIAM Symp. on Discrete Algorithms, pp. 451\u2013459. ACM, New York (2005)"},{"issue":"4","key":"38_CR8","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/0167-6377(82)90015-3","volume":"1","author":"M. Farber","year":"1982","unstructured":"Farber, M.: Independent Domination in Chordal Graphs. Operations Research Letters\u00a01(4), 134\u2013138 (1982)","journal-title":"Operations Research Letters"},{"issue":"4","key":"38_CR9","doi-asserted-by":"publisher","first-page":"892","DOI":"10.1137\/S0097539703427203","volume":"33","author":"J. Flum","year":"2004","unstructured":"Flum, J., Grohe, M.: The Parameterized Complexity of Counting Problems. SIAM Journal on Computing\u00a033(4), 892\u2013922 (2004)","journal-title":"SIAM Journal on Computing"},{"key":"38_CR10","doi-asserted-by":"crossref","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 J. Math.\u00a015, 835\u2013855 (1965)","journal-title":"Pacific J. Math."},{"issue":"2","key":"38_CR11","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F. Gavril","year":"1972","unstructured":"Gavril, F.: Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph. SIAM Journal on Computing\u00a01(2), 180\u2013187 (1972)","journal-title":"SIAM Journal on Computing"},{"key":"38_CR12","series-title":"Annals of Discrete Mathematics","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, 2nd edn. Annals of Discrete Mathematics, vol.\u00a057. Elsevier, Amsterdam (2004)","edition":"2"},{"issue":"4","key":"38_CR13","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1137\/S0097539789166880","volume":"25","author":"P.N. Klein","year":"1996","unstructured":"Klein, P.N.: Efficient Parallel Algorithms for Chordal Graphs. SIAM Journal on Computing\u00a025(4), 797\u2013827 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"38_CR14","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/0196-6774(84)90037-3","volume":"5","author":"J.Y.-T. Leung","year":"1984","unstructured":"Leung, J.Y.-T.: Fast Algorithms for Generating All Maximal Independent Sets of Interval, Circular-Arc and Chordal Graphs. Journal of Algorithms\u00a05, 22\u201335 (1984)","journal-title":"Journal of Algorithms"},{"key":"38_CR15","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1137\/0212053","volume":"12","author":"J.S. Provan","year":"1983","unstructured":"Provan, J.S., Ball, M.O.: The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected. SIAM Journal on Computing\u00a012, 777\u2013788 (1983)","journal-title":"SIAM Journal on Computing"},{"key":"38_CR16","volume-title":"Efficient Graph Representations","author":"J.P. Spinrad","year":"2003","unstructured":"Spinrad, J.P.: Efficient Graph Representations. American Mathematical Society, Providence (2003)"},{"issue":"2","key":"38_CR17","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1137\/S0097539797321602","volume":"31","author":"S.P. Vadhan","year":"2001","unstructured":"Vadhan, S.P.: The Complexity of Counting in Sparse, Regular, and Planar Graphs. SIAM Journal on Computing\u00a031(2), 398\u2013427 (2001)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11604686_38.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:04:29Z","timestamp":1619507069000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11604686_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540310006","9783540314684"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/11604686_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}