{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T07:40:11Z","timestamp":1736235611693,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540310006"},{"type":"electronic","value":"9783540314684"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11604686_33","type":"book-chapter","created":{"date-parts":[[2005,12,5]],"date-time":"2005-12-05T15:02:01Z","timestamp":1133794921000},"page":"374-384","source":"Crossref","is-referenced-by-count":0,"title":["Computing Branchwidth Via Efficient Triangulations and Blocks"],"prefix":"10.1007","author":[{"given":"Fedor","family":"Fomin","sequence":"first","affiliation":[]},{"given":"Fr\u00e9d\u00e9ric","family":"Mazoit","sequence":"additional","affiliation":[]},{"given":"Ioan","family":"Todinca","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"33_CR1","doi-asserted-by":"crossref","unstructured":"Beigel, R., Eppstein, D.: 3-coloring in time O(1.3446 n ): a no-MIS algorithm. In: Proceedings of the 36th IEEE Symposium on Foundations of Computer Science (FOCS 1995), pp. 444\u2013452 (1995)","DOI":"10.1109\/SFCS.1995.492575"},{"key":"33_CR2","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1016\/j.jalgor.2004.06.008","volume":"54","author":"R. Beigel","year":"2005","unstructured":"Beigel, R., Eppstein, D.: 3-coloring in time O(1.3289 n ). Journal of Algorithms\u00a054, 444\u2013453 (2005)","journal-title":"Journal of Algorithms"},{"key":"33_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci.\u00a0209, 1\u201345 (1998)","journal-title":"Theoret. Comput. Sci."},{"key":"33_CR4","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1137\/S089548019223992X","volume":"8","author":"H.L. Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Kloks, T., Kratsch, D.: Treewidth and pathwidth of permutation graphs. SIAM J. on Discrete Math.\u00a08, 606\u2013616 (1995)","journal-title":"SIAM J. on Discrete Math."},{"issue":"1","key":"33_CR5","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1137\/S0097539799359683","volume":"31","author":"V. Bouchitt\u00e9","year":"2001","unstructured":"Bouchitt\u00e9, V., Todinca, I.: Treewidth and minimum fill-in: grouping the minimal separators. SIAM J. on Computing\u00a031(1), 212\u2013232 (2001)","journal-title":"SIAM J. on Computing"},{"key":"33_CR6","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1016\/j.orl.2004.03.002","volume":"32","author":"J.M. Byskov","year":"2004","unstructured":"Byskov, J.M.: Enumerating maximal independent sets with applications to graph colouring. Operations Research Letters\u00a032, 547\u2013556 (2004)","journal-title":"Operations Research Letters"},{"key":"33_CR7","volume-title":"Introduction to algorithms","author":"T. Cormen","year":"1990","unstructured":"Cormen, T., Leiserson, C., Rivest, R.: Introduction to algorithms. The MIT press, Cambridge (1990)"},{"issue":"1","key":"33_CR8","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0304-3975(01)00174-8","volume":"289","author":"E. Dantsin","year":"2002","unstructured":"Dantsin, E., Goerdt, A., Hirsch, E.A., Kannan, R., Kleinberg, J., Papadimitriou, C., Raghavan, P., Sch\u00f6ning, U.: A deterministic (2\u2009\u2212\u20092\/(k\u2009+\u20091)) n algorithm for k-SAT based on local search. Theoretical Computer Science\u00a0289(1), 69\u201383 (2002)","journal-title":"Theoretical Computer Science"},{"key":"33_CR9","unstructured":"Eppstein, D.: Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction. In: Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms SODA 2001, pp. 329\u2013337 (2001)"},{"key":"33_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1007\/978-3-540-27836-8_49","volume-title":"Automata, Languages and Programming","author":"F. Fomin","year":"2004","unstructured":"Fomin, F., 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":"33_CR11","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 a path in a tree are exactly the chordal graphs. Journal of Combinatorial Theory\u00a016, 47\u201356 (1974)","journal-title":"Journal of Combinatorial Theory"},{"key":"33_CR12","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":"33_CR13","unstructured":"Iwama, K., Tamaki, S.: Improved upper bounds for 3-SAT. In: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms SODA 2004, p. 328 (2004)"},{"issue":"9","key":"33_CR14","doi-asserted-by":"publisher","first-page":"847","DOI":"10.1109\/TC.1986.1676847","volume":"35","author":"T. Jian","year":"1986","unstructured":"Jian, T.: An O(20.304n ) algorithm for solving maximum independent set problem. IEEE Transactions on Computers\u00a035(9), 847\u2013851 (1986)","journal-title":"IEEE Transactions on Computers"},{"key":"33_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/3-540-49116-3_16","volume-title":"STACS 99","author":"T. Kloks","year":"1999","unstructured":"Kloks, T., Kratochv\u00edl, J., M\u00fcller, H.: New branchwidth territories. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol.\u00a01563, pp. 173\u2013183. Springer, Heidelberg (1999)"},{"key":"33_CR16","unstructured":"Mazoit, F.: D\u00e9compositions algorithmiques des graphes. PhD thesis, \u00c9cole normale sup\u00e9rieure de Lyon (2004) (In French)"},{"issue":"1-3","key":"33_CR17","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/S0166-218X(97)00041-3","volume":"79","author":"A. Parra","year":"1997","unstructured":"Parra, A., Scheffler, P.: Characterizations and algorithmic applications of chordal graph embeddings. Discrete Appl. Math.\u00a079(1-3), 171\u2013188 (1997)","journal-title":"Discrete Appl. Math."},{"key":"33_CR18","doi-asserted-by":"crossref","unstructured":"Paturi, R., Pudlak, P., Saks, M.E., Zane, F.: An improved exponential-time algorithm for k-SAT. In: Proceedings of the 39th IEEE Symposium on Foundations of Computer Science FOCS 1998, pp. 628\u2013637 (1998)","DOI":"10.1109\/SFCS.1998.743513"},{"key":"33_CR19","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N. Robertson","year":"1991","unstructured":"Robertson, N., Seymour, P.: Graph minors X. Obstructions to tree decompositions. Journal of Combinatorial Theory Series B\u00a052, 153\u2013190 (1991)","journal-title":"Journal of Combinatorial Theory Series B"},{"issue":"3","key":"33_CR20","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0196-6774(86)90032-5","volume":"7","author":"J.M. Robson","year":"1986","unstructured":"Robson, J.M.: Algorithms for maximum independent sets. Journal of Algorithms\u00a07(3), 425\u2013440 (1986)","journal-title":"Journal of Algorithms"},{"key":"33_CR21","doi-asserted-by":"crossref","unstructured":"Schoning, U.: A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems. In: Proceedings of the 40th IEEE Symposium on Foundations of Computer Science FOCS 1999, pp. 410\u2013414 (1999)","DOI":"10.1109\/SFFCS.1999.814612"},{"key":"33_CR22","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"P.D. Seymour","year":"1994","unstructured":"Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica\u00a014, 217\u2013241 (1994)","journal-title":"Combinatorica"},{"issue":"3","key":"33_CR23","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1137\/0206038","volume":"6","author":"R. Tarjan","year":"1977","unstructured":"Tarjan, R., Trojanowski, A.: Finding a maximum independent set. SIAM Journal on Computing\u00a06(3), 537\u2013546 (1977)","journal-title":"SIAM Journal on Computing"},{"key":"33_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1227","DOI":"10.1007\/978-3-540-27836-8_101","volume-title":"Automata, Languages and Programming","author":"R. Williams","year":"2004","unstructured":"Williams, R.: A new algorithm for optimal constraint satisfaction and its implications. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 1227\u20131237. Springer, Heidelberg (2004)"},{"key":"33_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/3-540-36478-1_17","volume-title":"Combinatorial Optimization - Eureka, You Shrink!","author":"G.J. Woeginger","year":"2003","unstructured":"Woeginger, G.J.: Exact algorithms for NP-hard problems: A survey. In: J\u00fcnger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization - Eureka, You Shrink! LNCS, vol.\u00a02570, pp. 185\u2013207. Springer, Heidelberg (2003)"}],"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_33.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T05:10:22Z","timestamp":1736140222000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11604686_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540310006","9783540314684"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/11604686_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}