{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:37:50Z","timestamp":1725543470629},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540357537"},{"type":"electronic","value":"9783540357551"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11785293_39","type":"book-chapter","created":{"date-parts":[[2006,6,26]],"date-time":"2006-06-26T05:24:10Z","timestamp":1151299450000},"page":"423-434","source":"Crossref","is-referenced-by-count":3,"title":["Generalized Powers of Graphs and Their Algorithmic Use"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Brandst\u00e4dt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Feodor F.","family":"Dragan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yang","family":"Xiang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chenyu","family":"Yan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"39_CR1","first-page":"41","volume":"144","author":"G. Agnarsson","year":"2000","unstructured":"Agnarsson, G., Greenlaw, R., Halldorsson, M.M.: On powers of chordal graphs and their colorings. Congressus Numerantium\u00a0144, 41\u201365 (2000)","journal-title":"Congressus Numerantium"},{"key":"39_CR2","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1137\/S0895480100367950","volume":"16","author":"G. Agnarsson","year":"2003","unstructured":"Agnarsson, G., Halldorsson, M.M.: Coloring powers of planar graphs. SIAM J. Disc. Math.\u00a016, 651\u2013662 (2003)","journal-title":"SIAM J. Disc. Math."},{"key":"39_CR3","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0012-365X(94)00052-K","volume":"145","author":"H.J. Bandelt","year":"1995","unstructured":"Bandelt, H.J., Henkmann, A., Nicolai, F.: Powers of distance-hereditary graphs. Discrete Math.\u00a0145, 37\u201360 (1995)","journal-title":"Discrete Math."},{"key":"39_CR4","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1109\/TPDS.2003.1189581","volume":"14","author":"A.A. Bertossi","year":"2003","unstructured":"Bertossi, A.A., Pinotti, M.C., Tan, R.B.: Channel Assignment with Separation for Interference Avoidance in Wireless Networks. IEEE Trans. Parallel Distrib. Syst.\u00a014, 222\u2013235 (2003)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"39_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/3-540-46541-3_33","volume-title":"STACS 2000","author":"H.L. Bodlaender","year":"2000","unstructured":"Bodlaender, H.L., Kloks, T., Tan, R.B., van Leeuwen, J.: \u03bb-Coloring of Graphs. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol.\u00a01770, pp. 395\u2013406. Springer, Heidelberg (2000)"},{"key":"39_CR6","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0166-218X(97)00125-X","volume":"82","author":"A. Brandst\u00e4dt","year":"1998","unstructured":"Brandst\u00e4dt, A., Chepoi, V., Dragan, F.: The algorithmic use of hypertree structure and maximum neighborhood orderings. Disc. Appl. Math.\u00a082, 43\u201377 (1998)","journal-title":"Disc. Appl. Math."},{"key":"39_CR7","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1137\/S0895480193253415","volume":"11","author":"A. Brandst\u00e4dt","year":"1998","unstructured":"Brandst\u00e4dt, A., Dragan, F.F., Chepoi, V., Voloshin, V.I.: Dually Chordal Graphs. SIAM J. Discrete Math.\u00a011, 437\u2013455 (1998)","journal-title":"SIAM J. Discrete Math."},{"key":"39_CR8","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/S0304-3975(96)00091-6","volume":"172","author":"A. Brandst\u00e4dt","year":"1997","unstructured":"Brandst\u00e4dt, A., Dragan, F.F., Nicolai, F.: Homogeneously orderable graphs. Theoretical Computer Science\u00a0172, 209\u2013232 (1997)","journal-title":"Theoretical Computer Science"},{"key":"39_CR9","volume-title":"SIAM Monographs on Discrete Math. Appl.","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.: Graph Classes: A Survey. In: SIAM Monographs on Discrete Math. Appl. SIAM, Philadelphia (1999)"},{"key":"39_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/3-540-36385-8_12","volume-title":"Distributed Computing","author":"T. Calamoneri","year":"2002","unstructured":"Calamoneri, T., Petreschi, R.: On the Radiocoloring Problem. In: Das, S.K., Bhattacharya, S. (eds.) IWDC 2002. LNCS, vol.\u00a02571, pp. 118\u2013127. Springer, Heidelberg (2002)"},{"key":"39_CR11","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1137\/S0895480193245339","volume":"9","author":"G.J. Chang","year":"1996","unstructured":"Chang, G.J., Kuo, D.: The L(2,1)-labeling problem on graphs. SIAM J. Disc. Math.\u00a09, 309\u2013316 (1996)","journal-title":"SIAM J. Disc. Math."},{"key":"39_CR12","first-page":"161","volume":"67","author":"J.M. Chang","year":"2003","unstructured":"Chang, J.M., Ho, C.W., Ko, M.T.: Powers of Asteroidal Triple-free Graphs with Applications. Ars Combinatoria\u00a067, 161\u2013173 (2003)","journal-title":"Ars Combinatoria"},{"key":"39_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/3-540-46632-0_17","volume-title":"Algorithms and Computations","author":"J.M. Chang","year":"1999","unstructured":"Chang, J.M., Ho, C.W., Ko, M.T.: LexBFS-ordering in Asteroidal Triple-Free Graphs. In: Aggarwal, A.K., Pandu Rangan, C. (eds.) ISAAC 1999. LNCS, vol.\u00a01741, pp. 163\u2013172. Springer, Heidelberg (1999)"},{"key":"39_CR14","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/PL00007241","volume":"17","author":"M. Chen","year":"2001","unstructured":"Chen, M., Chang, G.J.: Families of Graphs Closed Under Taking Powers. Graphs and Combinatorics\u00a017, 207\u2013212 (2001)","journal-title":"Graphs and Combinatorics"},{"key":"39_CR15","first-page":"23","volume":"24B","author":"E. Dahlhaus","year":"1987","unstructured":"Dahlhaus, E., Duchet, P.: On strongly chordal graphs. Ars Comb.\u00a024B, 23\u201330 (1987)","journal-title":"Ars Comb."},{"key":"39_CR16","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0166-218X(92)90296-M","volume":"35","author":"P. Damaschke","year":"1992","unstructured":"Damaschke, P.: Distances in cocomparability graphs and their powers. Discrete Applied Mathematics\u00a035, 67\u201372 (1992)","journal-title":"Discrete Applied Mathematics"},{"key":"39_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jalgor.2004.09.002","volume":"57","author":"F.F. Dragan","year":"2005","unstructured":"Dragan, F.F.: Estimating All Pairs Shortest Paths in Restricted Graph Families: A Unified Approach. Journal of Algorithms\u00a057, 1\u201321 (2005)","journal-title":"Journal of Algorithms"},{"key":"39_CR18","first-page":"67","volume":"21","author":"P. Duchet","year":"1984","unstructured":"Duchet, P.: Classical perfect graphs. Ann. Discrete Math.\u00a021, 67\u201396 (1984)","journal-title":"Ann. Discrete Math."},{"key":"39_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1007\/3-540-46784-X_33","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"J. Fiala","year":"1999","unstructured":"Fiala, J., Kloks, T., Kratochv\u00edl, J.: Fixed-parameter complexity of \u03bb-labelings. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds.) WG 1999. LNCS, vol.\u00a01665, pp. 350\u2013363. Springer, Heidelberg (1999)"},{"key":"39_CR20","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/0166-218X(95)00091-5","volume":"69","author":"C. Flotow","year":"1996","unstructured":"Flotow, C.: On Powers of Circular Arc Graphs and Proper Circular Arc Graphs. Discrete Applied Mathematics\u00a069, 199\u2013207 (1996)","journal-title":"Discrete Applied Mathematics"},{"key":"39_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/3-540-44612-5_32","volume-title":"Mathematical Foundations of Computer Science 2000","author":"D. Fotakis","year":"2000","unstructured":"Fotakis, D., Nikoletseas, S.E., Papadopoulou, V.G., Spirakis, P.G.: NP-Completeness Results and Efficient Approximations for Radiocoloring in Planar Graphs. In: Nielsen, M., Rovan, B. (eds.) MFCS 2000. LNCS, vol.\u00a01893, pp. 363\u2013372. Springer, Heidelberg (2000)"},{"key":"39_CR22","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1137\/0601025","volume":"1","author":"M.R. Garey","year":"1980","unstructured":"Garey, M.R., Johnson, D.S., Miller, G.L., Papadimitriou, C.H.: The complexity of coloring circular arcs and chords. SIAM J. Alg. Disc. Meth.\u00a01, 216\u2013227 (1980)","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"39_CR23","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F. Gavril","year":"1972","unstructured":"Gavril, F.: Algorithms for min. coloring, max. clique, min. covering by cliques and max. independent set of a chordal graph. SIAM J. Comput.\u00a01, 180\u2013187 (1972)","journal-title":"SIAM J. Comput."},{"key":"39_CR24","doi-asserted-by":"publisher","first-page":"586","DOI":"10.1137\/0405048","volume":"5","author":"J.R. Griggs","year":"1992","unstructured":"Griggs, J.R., Yeh, R.K.: Labeling graphs with a condition at distance 2. SIAM J. Discrete Math.\u00a05, 586\u2013595 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"39_CR25","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel, M., Lovasz, L., Schrijver, A.: Polynomial algorithms for perfect graphs. In: Topics on perfect graphs, vol.\u00a088, pp. 325\u2013356","DOI":"10.1016\/S0304-0208(08)72943-8"},{"key":"39_CR26","unstructured":"Hayward, R., Spinrad, J., Sritharan, R.: Weakly chordal graph algorithms via handles. In: SODA 2000, pp. 42\u201349 (2000)"},{"key":"39_CR27","first-page":"306","volume":"70","author":"I.A. Karapetian","year":"1980","unstructured":"Karapetian, I.A.: On Coloring of Arc Graphs. Akademiia nauk Armianskoi SSR Doklady\u00a070, 306\u2013311 (1980)","journal-title":"Akademiia nauk Armianskoi SSR Doklady"},{"key":"39_CR28","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1137\/S0895480103424079","volume":"18","author":"D. Kr\u00e1l\u2019","year":"2004","unstructured":"Kr\u00e1l\u2019, D.: Coloring Powers of Chordal Graphs. SIAM Journal on Discrete Mathematics\u00a018, 451\u2013461 (2004)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"39_CR29","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/0166-218X(83)90068-9","volume":"6","author":"R. Laskar","year":"1983","unstructured":"Laskar, R., Shier, D.: Powers and centers of chordal graphs. Discrete Appl. Math.\u00a06, 139\u2013147 (1983)","journal-title":"Discrete Appl. Math."},{"key":"39_CR30","doi-asserted-by":"crossref","unstructured":"M\u00f6hring, R.H.: Algorithmic aspects of comparability graphs and interval graphs. In: Rival, I. (ed.) Graphs and Order, pp. 41\u2013102 (1985)","DOI":"10.1007\/978-94-009-5315-4_2"},{"key":"39_CR31","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1109\/90.222924","volume":"1","author":"S. Ramanathan","year":"1993","unstructured":"Ramanathan, S., Lloyd, E.L.: Scheduling Algorithms for Multihop Radio Networks. IEEE\/ACM Transactions on Networking\u00a01, 166\u2013172 (1993)","journal-title":"IEEE\/ACM Transactions on Networking"},{"key":"39_CR32","first-page":"147","volume":"34","author":"A. Raychaudhuri","year":"1992","unstructured":"Raychaudhuri, A.: On powers of strongly chordal and circular arc graphs. Ars Combin.\u00a034, 147\u2013160 (1992)","journal-title":"Ars Combin."},{"key":"39_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1007\/978-3-540-39890-5_32","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"I. Todinca","year":"2003","unstructured":"Todinca, I.: Coloring Powers of Graphs of Bounded Clique-Width. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol.\u00a02880, pp. 370\u2013382. Springer, Heidelberg (2003)"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11785293_39.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:19:25Z","timestamp":1619507965000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11785293_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540357537","9783540357551"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/11785293_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}