{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T23:30:28Z","timestamp":1725579028152},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642192210"},{"type":"electronic","value":"9783642192227"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-19222-7_18","type":"book-chapter","created":{"date-parts":[[2011,3,14]],"date-time":"2011-03-14T04:03:12Z","timestamp":1300075392000},"page":"167-180","source":"Crossref","is-referenced-by-count":0,"title":["Computing Role Assignments of Proper Interval Graphs in Polynomial Time"],"prefix":"10.1007","author":[{"given":"Pinar","family":"Heggernes","sequence":"first","affiliation":[]},{"given":"Pim","family":"van \u2019t Hof","sequence":"additional","affiliation":[]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"18_CR1","first-page":"82","volume-title":"Proceedings of STOC 1980","author":"D. Angluin","year":"1980","unstructured":"Angluin, D.: Local and global properties in networks of processors. In: Proceedings of STOC 1980, pp. 82\u201393. ACM, New York (1980)"},{"key":"18_CR2","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/0743-7315(89)90048-8","volume":"6","author":"H.L. Bodlaender","year":"1989","unstructured":"Bodlaender, H.L.: The classification of coverings of processor networks. Journal of Parallel and Distributed Computing\u00a06, 166\u2013182 (1989)","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"18_CR3","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.: Graph Classes: A Survey. SIAM, Philadelphia (1999)"},{"key":"18_CR4","first-page":"85","volume":"74","author":"J. Chalopin","year":"2006","unstructured":"Chalopin, J., M\u00e9tivier, Y., Zielonka, W.: Local computations in graphs: the case of cellular edge local computations. Fundamenta Informaticae\u00a074, 85\u2013114 (2006)","journal-title":"Fundamenta Informaticae"},{"key":"18_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/11917496_27","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"J. Chalopin","year":"2006","unstructured":"Chalopin, J., Paulusma, D.: Graph labelings derived from models in distributed computing. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, pp. 301\u2013312. Springer, Heidelberg (2006)"},{"key":"18_CR6","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs. Information and Computation\u00a085, 12\u201375 (1990)","journal-title":"Information and Computation"},{"key":"18_CR7","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0165-4896(91)90080-B","volume":"21","author":"M.G. Everett","year":"1991","unstructured":"Everett, M.G., Borgatti, S.: Role colouring a graph. Mathematical Social Sciences\u00a021, 183\u2013188 (1991)","journal-title":"Mathematical Social Sciences"},{"key":"18_CR8","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0166-218X(00)00387-5","volume":"113","author":"J. Fiala","year":"2001","unstructured":"Fiala, J., Kratochv\u00edl, J., Kloks, T.: Fixed-parameter complexity of \u03bb-labelings. Discrete Applied Mathematics\u00a0113, 59\u201372 (2001)","journal-title":"Discrete Applied Mathematics"},{"key":"18_CR9","doi-asserted-by":"publisher","first-page":"89","DOI":"10.7151\/dmgt.1159","volume":"22","author":"J. Fiala","year":"2002","unstructured":"Fiala, J., Kratochv\u00edl, J.: Partial covers of graphs. Discussiones Mathematicae Graph Theory\u00a022, 89\u201399 (2002)","journal-title":"Discussiones Mathematicae Graph Theory"},{"key":"18_CR10","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.tcs.2005.09.029","volume":"349","author":"J. Fiala","year":"2005","unstructured":"Fiala, J., Paulusma, D.: A complete complexity classification of the role assignment problem. Theoretical Computer Science\u00a0349, 67\u201381 (2005)","journal-title":"Theoretical Computer Science"},{"key":"18_CR11","doi-asserted-by":"publisher","first-page":"620","DOI":"10.1007\/s00224-009-9200-z","volume":"46","author":"J. Fiala","year":"2010","unstructured":"Fiala, J., Paulusma, D.: Comparing universal covers in polynomial time. Theory of Computing Systems\u00a046, 620\u2013635 (2010)","journal-title":"Theory of Computing Systems"},{"key":"18_CR12","doi-asserted-by":"publisher","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D. Fulkerson","year":"1965","unstructured":"Fulkerson, D., Gross, O.: Incidence matrices and interval graphs. Pacific Journal of Mathematics\u00a015, 835\u2013855 (1965)","journal-title":"Pacific Journal of Mathematics"},{"key":"18_CR13","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. W. H. Freeman and Co., New York (1979)"},{"key":"18_CR14","volume-title":"Annals of Discrete Mathematics","author":"M.C. Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. In: Annals of Discrete Mathematics, vol.\u00a057. Elsevier B.V., Amsterdam (2004)"},{"key":"18_CR15","doi-asserted-by":"publisher","first-page":"1737","DOI":"10.1016\/j.dam.2009.02.006","volume":"157","author":"L. Ibarra","year":"2009","unstructured":"Ibarra, L.: The clique-separator graph for chordal graphs. Discrete Applied Mathematics\u00a0157, 1737\u20131749 (2009)","journal-title":"Discrete Applied Mathematics"},{"key":"18_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jctb.1996.1743","volume":"71","author":"J. Kratochv\u00edl","year":"1997","unstructured":"Kratochv\u00edl, J., Proskurowski, A., Telle, J.A.: Covering regular graphs. Journal of Combinatorial Theory, Series B\u00a071, 1\u201316 (1997)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"18_CR17","doi-asserted-by":"crossref","first-page":"45","DOI":"10.4064\/fm-51-1-45-64","volume":"51","author":"C. Lekkerkerker","year":"1962","unstructured":"Lekkerkerker, C., Boland, D.: Representation of finite graphs by a set of intervals on the real line. Fundamenta Mathematicae\u00a051, 45\u201364 (1962)","journal-title":"Fundamenta Mathematicae"},{"key":"18_CR18","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1145\/322123.322125","volume":"26","author":"G.S. Lueker","year":"1979","unstructured":"Lueker, G.S., Booth, K.S.: A linear time algorithm for deciding interval graph isomorphism. Journal of the ACM\u00a026, 183\u2013195 (1979)","journal-title":"Journal of the ACM"},{"key":"18_CR19","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/S0165-4896(00)00064-0","volume":"41","author":"A. Pekec","year":"2001","unstructured":"Pekec, A., Roberts, F.S.: The role assignment model nearly fits most social networks. Mathematical Social Sciences\u00a041, 275\u2013293 (2001)","journal-title":"Mathematical Social Sciences"},{"unstructured":"Reidemeister, K.: Einf\u00fchrung in die kombinatorische Topologie. Braunschweig: Friedr. Vieweg. Sohn A.-G. XII, 209 S (1932)","key":"18_CR20"},{"key":"18_CR21","doi-asserted-by":"publisher","first-page":"903","DOI":"10.1016\/j.ejc.2009.06.003","volume":"31","author":"Y. Rieck","year":"2010","unstructured":"Rieck, Y., Yamashita, Y.: Finite planar emulators for K\n                4,5\u2009\u2212\u20094K\n                2 and K\n                1,2,2,2 and Fellows\u2019 conjecture. European Journal of Combinatorics\u00a031, 903\u2013907 (2010)","journal-title":"European Journal of Combinatorics"},{"key":"18_CR22","first-page":"139","volume-title":"Proof Techniques in Graph Theory","author":"F.S. Roberts","year":"1969","unstructured":"Roberts, F.S.: Indifference Graphs. In: Proof Techniques in Graph Theory, pp. 139\u2013146. Academic Press, New York (1969)"},{"key":"18_CR23","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/S0304-3975(03)00084-7","volume":"304","author":"L. Sheng","year":"2003","unstructured":"Sheng, L.: 2-Role assignments on triangulated graphs. Theoretical Computer Science\u00a0304, 201\u2013214 (2003)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-19222-7_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T06:31:39Z","timestamp":1558420299000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-19222-7_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642192210","9783642192227"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-19222-7_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}