{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T04:14:03Z","timestamp":1743653643461,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642315848"},{"type":"electronic","value":"9783642315855"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31585-5_54","type":"book-chapter","created":{"date-parts":[[2012,6,23]],"date-time":"2012-06-23T11:56:29Z","timestamp":1340452589000},"page":"610-622","source":"Crossref","is-referenced-by-count":6,"title":["k-Chordal Graphs: From Cops and Robber to Compact Routing via Treewidth"],"prefix":"10.1007","author":[{"given":"Adrian","family":"Kosowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bi","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicolas","family":"Nisse","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karol","family":"Suchan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"54_CR1","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Alg. Discrete Methods\u00a08, 277\u2013284 (1987)","journal-title":"SIAM J. Alg. Discrete Methods"},{"key":"54_CR2","doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C.: Object location using path separators. In: PODC, pp. 188\u2013197. ACM (2006)","DOI":"10.1145\/1146381.1146411"},{"key":"54_CR3","doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C., Malkhi, D.: On space-stretch trade-offs: Lower bounds. In: SPAA, pp. 217\u2013224 (2006)","DOI":"10.1145\/1148109.1148143"},{"key":"54_CR4","doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C., Goldberg, A.V., Malkhi, D.: Routing in networks with low doubling dimension. In: ICDCS, p. 75 (2006)","DOI":"10.1109\/ICDCS.2006.72"},{"key":"54_CR5","doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C., Malkhi, D., Nisan, N., Thorup, M.: Compact name-independent routing with minimum stretch. ACM T. Alg.\u00a04(3) (2008)","DOI":"10.1145\/1367064.1367077"},{"issue":"2","key":"54_CR6","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms\u00a021(2), 358\u2013402 (1996)","journal-title":"J. Algorithms"},{"key":"54_CR7","doi-asserted-by":"crossref","unstructured":"Bonato, A., Nowakovski, R.: The game of Cops and Robber on Graphs. American Math. Soc. (2011)","DOI":"10.1090\/stml\/061"},{"issue":"1-2","key":"54_CR8","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. Theor. Comput. Sci.\u00a0209(1-2), 1\u201345 (1998)","journal-title":"Theor. Comput. Sci."},{"issue":"1-3","key":"54_CR9","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0166-218X(97)00031-0","volume":"79","author":"H.L. Bodlaender","year":"1997","unstructured":"Bodlaender, H.L., Thilikos, D.M.: Treewidth for graphs with small chordality. Disc. Ap. Maths\u00a079(1-3), 45\u201361 (1997)","journal-title":"Disc. Ap. Maths"},{"key":"54_CR10","doi-asserted-by":"crossref","unstructured":"Chen, Y., Flum, J.: On parameterized path and chordless path problems. In: CCC, pp. 250\u2013263 (2007)","DOI":"10.1109\/CCC.2007.21"},{"key":"54_CR11","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0304-3975(93)90064-Z","volume":"109","author":"B. Courcelle","year":"1993","unstructured":"Courcelle, B., Mosbah, M.: Monadic second-order evaluations on tree-decomposable graphs. TCS\u00a0109, 49\u201382 (1993)","journal-title":"TCS"},{"issue":"1-3","key":"54_CR12","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.disc.2004.11.016","volume":"299","author":"N.E. Clarke","year":"2005","unstructured":"Clarke, N.E., Nowakowski, R.J.: Tandem-win graphs. Discrete Mathematics\u00a0299(1-3), 56\u201364 (2005)","journal-title":"Discrete Mathematics"},{"issue":"16","key":"54_CR13","doi-asserted-by":"publisher","first-page":"2008","DOI":"10.1016\/j.disc.2005.12.060","volume":"307","author":"Y. Dourisboure","year":"2007","unstructured":"Dourisboure, Y., Gavoille, C.: Tree-decompositions with bags of small diameter. Discrete Mathematics\u00a0307(16), 2008\u20132029 (2007)","journal-title":"Discrete Mathematics"},{"key":"54_CR14","doi-asserted-by":"crossref","unstructured":"de Montgolfier, F., Soto, M., Viennot, L.: Treewidth and hyperbolicity of the internet. In: NCA, pp. 25\u201332. IEEE Comp. Soc. (2011)","DOI":"10.1109\/NCA.2011.11"},{"issue":"2","key":"54_CR15","first-page":"277","volume":"9","author":"Y. Dourisboure","year":"2005","unstructured":"Dourisboure, Y.: Compact routing schemes for generalised chordal graphs. J. of Graph Alg. and App.\u00a09(2), 277\u2013297 (2005)","journal-title":"J. of Graph Alg. and App."},{"key":"54_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1007\/3-540-48224-5_62","volume-title":"Automata, Languages and Programming","author":"P. Fraigniaud","year":"2001","unstructured":"Fraigniaud, P., Gavoille, C.: Routing in Trees. In: Yu, Y., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 757\u2013772. Springer, Heidelberg (2001)"},{"key":"54_CR17","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-1-4613-9586-7_3","volume":"8","author":"M. Gromov","year":"1987","unstructured":"Gromov, M.: Hyperbolic groups. Essays in Group Theory\u00a08, 75\u2013263 (1987)","journal-title":"Essays in Group Theory"},{"key":"54_CR18","doi-asserted-by":"crossref","unstructured":"Kobayashi, Y., Kawarabayashi, K.: Algorithms for finding an induced cycle in planar graphs and bounded genus graphs. In: 20th Annual ACM-SIAM Symp. on Discrete Alg. (SODA), pp. 1146\u20131155. SIAM (2009)","DOI":"10.1137\/1.9781611973068.124"},{"key":"54_CR19","doi-asserted-by":"crossref","unstructured":"Kosowski, A., Li, B., Nisse, N., Suchan, K.: k-chordal graphs: from cops and robber to compact routing via treewidth, Report, INRIA-RR7888 (2012), http:\/\/www-sop.inria.fr\/members\/Bi.Li\/RR-7888.pdf","DOI":"10.1007\/978-3-642-31585-5_54"},{"issue":"2","key":"54_CR20","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1145\/1639562.1639568","volume":"37","author":"D.V. Krioukov","year":"2009","unstructured":"Krioukov, D.V., Papadopoulos, F., Bogu\u00f1\u00e1, M., Vahdat, A.: Greedy forwarding in scale-free networks embedded in hyperbolic metric spaces. SIGMETRICS Performance Evaluation Review\u00a037(2), 15\u201317 (2009)","journal-title":"SIGMETRICS Performance Evaluation Review"},{"key":"54_CR21","doi-asserted-by":"crossref","unstructured":"Nisse, N., Suchan, K., Rapaport, I.: Distributed computing of efficient routing schemes in generalized chordal graphs. TCS (to appear, 2012)","DOI":"10.1016\/j.tcs.2012.01.006"},{"issue":"6684","key":"54_CR22","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"D.J. Watts","year":"1998","unstructured":"Watts, D.J., Strogatz, S.: Collective dynamics of \u2019small-world\u2019 networks. Nature\u00a0393(6684), 440\u2013442 (1998)","journal-title":"Nature"},{"key":"54_CR23","doi-asserted-by":"crossref","unstructured":"Wu, Y., Zhang, C.: Hyperbolicity and chordality of a graph. Electr. J. Comb. 18(1) (2011)","DOI":"10.37236\/530"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31585-5_54.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,2]],"date-time":"2025-04-02T13:49:39Z","timestamp":1743601779000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31585-5_54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642315848","9783642315855"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31585-5_54","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}