{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:13:24Z","timestamp":1725516804231},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540697329"},{"type":"electronic","value":"9783540697336"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-69733-6_45","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"458-467","source":"Crossref","is-referenced-by-count":3,"title":["On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints"],"prefix":"10.1007","author":[{"given":"Shuji","family":"Kijima","sequence":"first","affiliation":[]},{"given":"Masashi","family":"Kiyomi","sequence":"additional","affiliation":[]},{"given":"Yoshio","family":"Okamoto","sequence":"additional","affiliation":[]},{"given":"Takeaki","family":"Uno","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"45_CR1","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0166-218X(95)00026-N","volume":"65","author":"D. Avis","year":"1996","unstructured":"Avis, D., Fukuda, K.: Reverse Search for Enumeration. Discrete Applied Mathematics\u00a065, 21\u201346 (1996)","journal-title":"Discrete Applied Mathematics"},{"key":"45_CR2","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"G.A. Dirac","year":"1961","unstructured":"Dirac, G.A.: On Rigid Circuit Graphs. Abhandl. Math. Seminar Univ. Hamburg\u00a025, 71\u201376 (1961)","journal-title":"Abhandl. Math. Seminar Univ. Hamburg"},{"key":"45_CR3","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 Journal of Mathematics\u00a015, 835\u2013855 (1965)","journal-title":"Pacific Journal of Mathematics"},{"key":"45_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1007\/978-3-540-27836-8_49","volume-title":"Automata, Languages and Programming","author":"F.V. Fomin","year":"2004","unstructured":"Fomin, F.V., Kratsch, D., Todinca, I.: Exact (Exponential) Algorithms for Treewidth and Minimum Fill-in. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 568\u2013580. Springer, Heidelberg (2004)"},{"key":"45_CR5","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1137\/S1052623400366218","volume":"11","author":"M. Fukuda","year":"2000","unstructured":"Fukuda, M., Kojima, M., Murota, K., Nakata, K.: Exploiting Sparsity in Semidefinite Programming via Matrix Completion I: General Framework. SIAM Journal on Optimization\u00a011, 647\u2013674 (2000)","journal-title":"SIAM Journal on Optimization"},{"key":"45_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":"45_CR7","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1006\/jagm.1995.1047","volume":"19","author":"M.C. Golumbic","year":"1995","unstructured":"Golumbic, M.C., Kaplan, H., Shamir, R.: Graph Sandwich Problems. Journal of Algorithms\u00a019, 449\u2013473 (1995)","journal-title":"Journal of Algorithms"},{"key":"45_CR8","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/j.disc.2005.12.003","volume":"306","author":"P. Heggernes","year":"2006","unstructured":"Heggernes, P.: Minimal Triangulations of Graphs: A Survey. Discrete Mathematics\u00a0306, 297\u2013317 (2006)","journal-title":"Discrete Mathematics"},{"key":"45_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/978-3-540-70918-3_21","volume-title":"STACS 2007","author":"P. Heggernes","year":"2007","unstructured":"Heggernes, P., Suchan, K., Todinca, I., Villanger, Y.: Characterizing Minimal Interval Vompletions: towards Better Understanding of Profile and Pathwidth. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 236\u2013247. Springer, Heidelberg (2007)"},{"key":"45_CR10","unstructured":"Ibarra, L.: Fully Dynamic Algorithms for Chordal Graphs. In: Proc. of SODA 1999, pp. 923\u2013924 (1999)"},{"key":"45_CR11","unstructured":"Kijima, S., Kiyomi, M., Okamoto, Y., Uno, T.: On Counting, Sampling, and Listing of Chordal Graphs with Edge Constrains. RIMS-1610, Kyoto University (preprint, 2007), http:\/\/www.kurims.kyoto-u.ac.jp\/preprint\/file\/RIMS1610.pdf"},{"key":"45_CR12","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1093\/ietisy\/e89-d.2.763","volume":"E89-D","author":"M. Kiyomi","year":"2006","unstructured":"Kiyomi, M., Uno, T.: Generating Chordal Graphs Included in Given Graphs. IEICE Transactions on Information and Systems\u00a0E89-D, 763\u2013770 (2006)","journal-title":"IEICE Transactions on Information and Systems"},{"key":"45_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/11917496_7","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M. Kiyomi","year":"2006","unstructured":"Kiyomi, M., Kijima, S., Uno, T.: Listing Chordal Graphs and Interval Graphs. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, pp. 68\u201377. Springer, Heidelberg (2006)"},{"key":"45_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1007\/3-540-57273-2_61","volume-title":"Algorithms - ESA \u201993","author":"T. Kloks","year":"1993","unstructured":"Kloks, T., Bodlaender, H.L., M\u00fcller, H., Kratsch, D.: Computing Treewidth and Minimum Fill-in: All You Need are the Minimal Separators. In: Lengauer, T. (ed.) ESA 1993. LNCS, vol.\u00a0726, pp. 260\u2013271. Springer, Heidelberg (1993)"},{"key":"45_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1007\/BFb0049435","volume-title":"Algorithms - ESA \u201994","author":"T. Kloks","year":"1994","unstructured":"Kloks, T., Bodlaender, H.L., M\u00fcller, H., Kratsch, D.: Erratum to the ESA 1993 proceedings. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol.\u00a0855, p. 508. Springer, Heidelberg (1994)"},{"key":"45_CR16","doi-asserted-by":"crossref","first-page":"45","DOI":"10.4064\/fm-51-1-45-64","volume":"51","author":"C.G. Leckerkerker","year":"1962","unstructured":"Leckerkerker, C.G., Boland, J.C.: Representation of a Finite Graph by a Set of Intervals on the Real Line. Fundamenta Mathematicae\u00a051, 45\u201364 (1962)","journal-title":"Fundamenta Mathematicae"},{"key":"45_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/11917496_4","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"D. Marx","year":"2006","unstructured":"Marx, D.: Chordal Deletion is Fixed-Parameter Tractable. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, pp. 37\u201348. Springer, Heidelberg (2006)"},{"key":"45_CR18","doi-asserted-by":"publisher","first-page":"1067","DOI":"10.1137\/S0097539798336073","volume":"30","author":"A. Natanzon","year":"2000","unstructured":"Natanzon, A., Shamir, R., Sharan, R.: A Polynomial Approximation Algorithm for the Minimum Fill-in Problem. SIAM Journal on Computing\u00a030, 1067\u20131079 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"45_CR19","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/S0166-218X(00)00391-7","volume":"113","author":"A. Natanzon","year":"2001","unstructured":"Natanzon, A., Shamir, R., Sharan, R.: Complexity Classification of Some Edge Modification Problems. Discrete Applied Mathematics\u00a0113, 109\u2013128 (2001)","journal-title":"Discrete Applied Mathematics"},{"key":"45_CR20","doi-asserted-by":"crossref","unstructured":"Pedersen, T., Bruce, R.F., Wiebe, J.: Sequential Model Selection for Word Sense Disambiguation. In: Proceedings of the Fifth Conference on Applied Natural Language Processing (ANLP 1997), pp. 388\u2013395 (1997)","DOI":"10.3115\/974557.974613"},{"key":"45_CR21","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.: Graph Minors II. Algorithmic Aspects of Tree-Width. Journal of Algorithms\u00a07, 309\u2013322 (1986)","journal-title":"Journal of Algorithms"},{"key":"45_CR22","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/B978-1-4832-3187-7.50018-0","volume-title":"Graph Theory and Computing","author":"D.J. Rose","year":"1972","unstructured":"Rose, D.J.: A Graph-Theoretic Study of the Numerical Solution of Sparse Positive Definite Systems of Linear Equations. In: Read, R.C. (ed.) Graph Theory and Computing, pp. 183\u2013217. Academic Press, New York (1972)"},{"key":"45_CR23","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D.J. Rose","year":"1976","unstructured":"Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic Aspects of Vertex Elimination on Graphs. SIAM Journal on Computing\u00a05, 266\u2013283 (1976)","journal-title":"SIAM Journal on Computing"},{"key":"45_CR24","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0323-0","volume-title":"Algorithms for Random Generation and Counting: A Markov Chain Approach","author":"A. Sinclair","year":"1993","unstructured":"Sinclair, A.: Algorithms for Random Generation and Counting: A Markov Chain Approach. Birkh\u00e4user, Boston (1993)"},{"key":"45_CR25","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"R.E. Tarjan","year":"1984","unstructured":"Tarjan, R.E., Yannakakis, M.: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs. SIAM Journal on Computing\u00a013, 566\u2013579 (1984)","journal-title":"SIAM Journal on Computing"},{"key":"45_CR26","unstructured":"Takemura, A., Endo, Y.: Evaluation of Per-record Identification Risk and Swappability of Records in a Microdata Set via Decomposable Models. arXiv:math.ST\/0603609"},{"key":"45_CR27","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"V.G. Valiant","year":"1979","unstructured":"Valiant, V.G.: The Complexity of Computing the Permanent. Theoretical Computer Science\u00a08, 189\u2013201 (1979)","journal-title":"Theoretical Computer Science"},{"key":"45_CR28","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"V.G. Valiant","year":"1979","unstructured":"Valiant, V.G.: The Complexity of Enumeration and Reliability Problems. SIAM Journal on Computing\u00a08, 410\u2013421 (1979)","journal-title":"SIAM Journal on Computing"},{"key":"45_CR29","doi-asserted-by":"crossref","unstructured":"Yamashita, N.: Sparse Quasi-Newton Updates with Positive Definite Matrix Completion. Mathematical Programming (2007), http:\/\/www.springerlink.com\/content\/28271224t1nt3580\/","DOI":"10.1007\/s10107-007-0137-1"},{"key":"45_CR30","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1137\/0602010","volume":"2","author":"M. Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Computing the Minimum Fill-in is NP-Complete. SIAM Journal on Algebraic and Discrete Methods\u00a02, 77\u201379 (1981)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"45_CR31","volume-title":"Graphical Models in Applied Multivariate Statistics","author":"J. Whittaker","year":"1990","unstructured":"Whittaker, J.: Graphical Models in Applied Multivariate Statistics. Wiley, New York (1990)"},{"key":"45_CR32","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF02582944","volume":"1","author":"N.C. Wormald","year":"1985","unstructured":"Wormald, N.C.: Counting Labeled Chordal Graphs. Graphs and Combinatorics\u00a01, 193\u2013200 (1985)","journal-title":"Graphs and Combinatorics"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-69733-6_45.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T05:02:18Z","timestamp":1605762138000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-69733-6_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540697329","9783540697336"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-69733-6_45","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}