{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:45:38Z","timestamp":1781077538372,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540709176","type":"print"},{"value":"9783540709183","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70918-3_4","type":"book-chapter","created":{"date-parts":[[2007,5,23]],"date-time":"2007-05-23T19:41:23Z","timestamp":1179949283000},"page":"37-48","source":"Crossref","is-referenced-by-count":20,"title":["Compact Forbidden-Set Routing"],"prefix":"10.1007","author":[{"given":"Bruno","family":"Courcelle","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrew","family":"Twigg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"4_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/378580.378581","volume-title":"SPAA \u201901: Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures","author":"M. Thorup","year":"2001","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: SPAA \u201901: Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, Crete Island, Greece, pp. 1\u201310. ACM Press, New York (2001), doi:10.1145\/378580.378581"},{"key":"4_CR2","unstructured":"Varadhan, K., Govindan, R., Estrin, D.: Persistent route oscillations in inter-domain routing. Technical report, USC\/ISI (1996)"},{"issue":"2","key":"4_CR3","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1109\/90.993304","volume":"10","author":"T.G. Griffin","year":"2002","unstructured":"Griffin, T.G., Shepherd, F.B., Wilfong, G.: The stable paths problem and interdomain routing. IEEE\/ACM Trans. Netw.\u00a010(2), 232\u2013243 (2002)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"4_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/11600930_18","volume-title":"Internet and Network Economics","author":"J. Feigenbaum","year":"2005","unstructured":"Feigenbaum, J., et al.: Subjective-cost policy routing. In: Deng, X., Ye, Y. (eds.) WINE 2005. LNCS, vol.\u00a03828, pp. 174\u2013183. Springer, Heidelberg (2005)"},{"issue":"1","key":"4_CR5","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0166-218X(02)00421-3","volume":"131","author":"B. Courcelle","year":"2003","unstructured":"Courcelle, B., Vanicat, R.: Query efficient implementation of graphs of bounded clique-width. Discrete Applied Mathematics\u00a0131(1), 129\u2013150 (2003)","journal-title":"Discrete Applied Mathematics"},{"key":"4_CR6","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1145\/777412.777443","volume-title":"SPAA \u201903: Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures","author":"A. Gupta","year":"2003","unstructured":"Gupta, A., Kumar, A., Thorup, M.: Tree based mpls routing. In: SPAA \u201903: Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, San Diego, California, USA, pp. 193\u2013199. ACM Press, New York (2003), doi:10.1145\/777412.777443"},{"key":"4_CR7","unstructured":"Courcelle, B.: Graph decompositions. Chapter of a book in preparation (2006), Available at \n                    \n                      http:\/\/www.labri.fr\/perso\/courcell\/Textes\/ChapitreDecArbos.pdf"},{"issue":"5","key":"4_CR8","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/174147.169807","volume":"40","author":"S. Arnborg","year":"1993","unstructured":"Arnborg, S., et al.: An algebraic theory of graph reduction. J. ACM\u00a040(5), 1134\u20131164 (1993), doi:10.1145\/174147.169807","journal-title":"J. ACM"},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"H.L. Bodlaender","year":"1989","unstructured":"Bodlaender, H.L.: NC-algorithms for graphs with small treewidth. In: van Leeuwen, J. (ed.) WG 1988. LNCS, vol.\u00a0344, pp. 1\u201310. Springer, Heidelberg (1989)"},{"issue":"4","key":"4_CR10","doi-asserted-by":"publisher","first-page":"825","DOI":"10.1137\/S0097539701385351","volume":"34","author":"D.G. Corneil","year":"2005","unstructured":"Corneil, D.G., Rotics, U.: On the relationship between clique-width and treewidth. SIAM J. Comput.\u00a034(4), 825\u2013847 (2005)","journal-title":"SIAM J. Comput."},{"issue":"2-3","key":"4_CR11","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0166-218X(94)90026-4","volume":"54","author":"E. Wanke","year":"1994","unstructured":"Wanke, E.: k-nlc graphs and polynomial algorithms. Discrete Applied Mathematics\u00a054(2-3), 251\u2013266 (1994)","journal-title":"Discrete Applied Mathematics"},{"issue":"1-3","key":"4_CR12","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B. Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math.\u00a0101(1-3), 77\u2013114 (2000)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"4_CR13","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1137\/0405049","volume":"5","author":"S. Kannan","year":"1992","unstructured":"Kannan, S., Naor, M., Rudich, S.: Implicit representation of graphs. SIAM J. Discret. Math.\u00a05(4), 596\u2013603 (1992), doi:10.1137\/0405049","journal-title":"SIAM J. Discret. Math."},{"key":"4_CR14","volume-title":"STOC 2006, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing","author":"M.R. Fellows","year":"2006","unstructured":"Fellows, M.R., et al.: Clique-width minimization is np-hard. In: STOC 2006, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, Seattle, Washington, ACM Press, New York (2006)"},{"key":"4_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/11604686_5","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"S Oum il","year":"2005","unstructured":"Oum, S.-i.: Approximating rank-width and clique-width quickly. In: Kratsch, D. (ed.) WG 2005. LNCS, vol.\u00a03787, pp. 49\u201358. Springer, Heidelberg (2005)"}],"container-title":["Lecture Notes in Computer Science","STACS 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70918-3_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T00:11:54Z","timestamp":1605744714000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70918-3_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540709176","9783540709183"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70918-3_4","relation":{},"subject":[]}}