{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:55:37Z","timestamp":1725569737784},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642169250"},{"type":"electronic","value":"9783642169267"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"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":[[2010]]},"DOI":"10.1007\/978-3-642-16926-7_16","type":"book-chapter","created":{"date-parts":[[2010,11,10]],"date-time":"2010-11-10T07:48:26Z","timestamp":1289375306000},"page":"159-170","source":"Crossref","is-referenced-by-count":6,"title":["On the Boolean-Width of a Graph: Structure and Applications"],"prefix":"10.1007","author":[{"given":"Isolde","family":"Adler","sequence":"first","affiliation":[]},{"given":"Binh-Minh","family":"Bui-Xuan","sequence":"additional","affiliation":[]},{"given":"Yuri","family":"Rabinovich","sequence":"additional","affiliation":[]},{"given":"Gabriel","family":"Renault","sequence":"additional","affiliation":[]},{"given":"Jan Arne","family":"Telle","sequence":"additional","affiliation":[]},{"given":"Martin","family":"Vatshelle","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","unstructured":"Bodlaender, H., Koster, A.: Treewidth Computations I Upper Bounds. Technical Report UU-CS-2008-032, Department of Information and Computing Sciences, Utrecht University (2008)"},{"key":"16_CR2","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-642-11269-0_5","volume-title":"4th International Workshop on Parameterized and Exact Computation (IWPEC 2009)","author":"B.-M. Bui-Xuan","year":"2009","unstructured":"Bui-Xuan, B.-M., Telle, J.A., Vatshelle, M.: Boolean-width of graphs. In: 4th International Workshop on Parameterized and Exact Computation (IWPEC 2009). LNCS, vol.\u00a05917, pp. 61\u201374. Springer, Heidelberg (2009)"},{"issue":"7","key":"16_CR3","doi-asserted-by":"publisher","first-page":"809","DOI":"10.1016\/j.dam.2009.09.009","volume":"158","author":"B.-M. Bui-Xuan","year":"2010","unstructured":"Bui-Xuan, B.-M., Telle, J.A., Vatshelle, M.: H-join decomposable graphs and algorithms with runtime single exponential in rankwidth. Discrete Applied Mathematics\u00a0158(7), 809\u2013819 (2010)","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"16_CR4","doi-asserted-by":"publisher","first-page":"825","DOI":"10.1137\/S0097539701385351","volume":"34","author":"D. Corneil","year":"2005","unstructured":"Corneil, D., Rotics, U.: On the relationship between clique-width and treewidth. SIAM Journal on Computing\u00a034(4), 825\u2013847 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: Graph rewriting: An algebraic and logic approach. In: Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B), pp. 193\u2013242 (1990)","DOI":"10.1016\/B978-0-444-88074-1.50010-X"},{"key":"16_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/11841036_27","volume-title":"Algorithms \u2013 ESA 2006","author":"F. Dorn","year":"2006","unstructured":"Dorn, F.: Dynamic programming and fast matrix multiplication. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 280\u2013291. Springer, Heidelberg (2006)"},{"key":"16_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R. Downey","year":"1999","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"16_CR8","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"issue":"7","key":"16_CR9","doi-asserted-by":"publisher","first-page":"851","DOI":"10.1016\/j.dam.2009.10.018","volume":"158","author":"R. Ganian","year":"2010","unstructured":"Ganian, R., Hlin\u011bn\u00fd, P.: On Parse Trees and Myhill-Nerode-type Tools for handling Graphs of Bounded Rank-width. Discrete Applied Mathematics\u00a0158(7), 851\u2013867 (2010)","journal-title":"Discrete Applied Mathematics"},{"issue":"1-3","key":"16_CR10","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1016\/S0304-3975(02)00725-9","volume":"299","author":"M. Gerber","year":"2003","unstructured":"Gerber, M., Kobler, D.: Algorithms for vertex-partitioning problems on graphs with fixed clique-width. Theoretical Computer Science\u00a0299(1-3), 719\u2013734 (2003)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"16_CR11","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1093\/comjnl\/bxm052","volume":"51","author":"P. Hlin\u011bn\u00fd","year":"2008","unstructured":"Hlin\u011bn\u00fd, P., Oum, S., Seese, D., Gottlob, G.: Width parameters beyond tree-width and their applications. The Computer Journal\u00a051(3), 326\u2013362 (2008)","journal-title":"The Computer Journal"},{"key":"16_CR12","unstructured":"Hvidevold, E.: Implementation of heuristics for computing boolean-width, Master thesis, University of Bergen (September 2010) (to appear)"},{"key":"16_CR13","first-page":"39","volume":"132","author":"\u00d6. Johansson","year":"1998","unstructured":"Johansson, \u00d6.: Clique-decomposition, NLC-decomposition and modular decomposition \u2013 Relatiohships and results for random graphs. Congressus Numerantium\u00a0132, 39\u201360 (1998)","journal-title":"Congressus Numerantium"},{"issue":"17","key":"16_CR14","doi-asserted-by":"publisher","first-page":"2328","DOI":"10.1016\/j.dam.2007.06.011","volume":"155","author":"M. Kant\u00e9","year":"2007","unstructured":"Kant\u00e9, M.: Vertex-minor reductions can simulate edge contractions. Discrete Applied Mathematics\u00a0155(17), 2328\u20132340 (2007)","journal-title":"Discrete Applied Mathematics"},{"key":"16_CR15","volume-title":"Boolean matrix theory and applications","author":"K.H. Kim","year":"1982","unstructured":"Kim, K.H.: Boolean matrix theory and applications. Marcel Dekker, New York (1982)"},{"key":"16_CR16","unstructured":"Kloks, T., Bodlaender, H.: Only few graphs have bounded treewidth. Technical Report UU-CS-92-35, Department of Information and Computing Sciences, Utrecht University (1992)"},{"issue":"2-3","key":"16_CR17","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/S0166-218X(02)00198-1","volume":"126","author":"D. Kobler","year":"2003","unstructured":"Kobler, D., Rotics, U.: Edge dominating set and colorings on graphs with fixed clique-width. Discrete Applied Mathematics\u00a0126(2-3), 197\u2013221 (2003); Abstract at SODA 2001","journal-title":"Discrete Applied Mathematics"},{"key":"16_CR18","unstructured":"Lee, C., Lee, J., Oum, S.: Rank-width of Random Graphs, http:\/\/arxiv.org\/pdf\/1001.0461"},{"key":"16_CR19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"issue":"3","key":"16_CR20","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1002\/jgt.20280","volume":"57","author":"S. Oum","year":"2008","unstructured":"Oum, S.: Rank-width is less than or equal to branch-width. Journal of Graph Theory\u00a057(3), 239\u2013244 (2008)","journal-title":"Journal of Graph Theory"},{"key":"16_CR21","unstructured":"Rabinovich, Y., Telle, J.A.: On the boolean-width of a graph: structure and applications, http:\/\/arxiv.org\/pdf\/0908.2765"},{"key":"16_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1007\/978-3-642-04128-0_51","volume-title":"Algorithms - ESA 2009","author":"J. Rooij","year":"2009","unstructured":"Rooij, J., Bodlaender, H., Rossmanith, P.: Dynamic programming on tree decompositions using generalised fast subset convolution. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 566\u2013577. Springer, Heidelberg (2009)"},{"issue":"4","key":"16_CR23","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1137\/S0895480194275825","volume":"10","author":"J.A. Telle","year":"1997","unstructured":"Telle, J.A., Proskurowski, A.: Algorithms for vertex partitioning problems on partial k-trees. SIAM Journal on Discrete Mathematics\u00a010(4), 529\u2013550 (1997)","journal-title":"SIAM Journal on Discrete Mathematics"}],"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\/978-3-642-16926-7_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T05:06:00Z","timestamp":1559797560000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16926-7_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642169250","9783642169267"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16926-7_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}