{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T15:39:02Z","timestamp":1772811542673,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642258695","type":"print"},{"value":"9783642258701","type":"electronic"}],"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-25870-1_18","type":"book-chapter","created":{"date-parts":[[2011,11,30]],"date-time":"2011-11-30T13:32:45Z","timestamp":1322659965000},"page":"191-202","source":"Crossref","is-referenced-by-count":16,"title":["Alternation Graphs"],"prefix":"10.1007","author":[{"given":"Magn\u00fas M.","family":"Halld\u00f3rsson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergey","family":"Kitaev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Artem","family":"Pyatkin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"18_CR1","unstructured":"Brandst\u00e4dt, A., Bang Lee, V., Spinrad, J.P.: Graph Classes: A Survey. Monographs on Discrete Mathematics and Applications. SIAM (1987)"},{"issue":"3","key":"18_CR2","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1016\/j.jal.2007.05.001","volume":"6","author":"B. Courcelle","year":"2008","unstructured":"Courcelle, B.: Circle graphs and Monadic Second-order logic. J. Applied Logic\u00a06(3), 416\u2013442 (2008)","journal-title":"J. Applied Logic"},{"key":"18_CR3","unstructured":"Draper, D.L., Jonsson, A.K., Clements, D.P., Joslin, D.E.: Cyclic Scheduling. In: Proc. IJCAI (1999)"},{"issue":"2","key":"18_CR4","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/j.jcta.2007.06.003","volume":"115","author":"R. Graham","year":"2008","unstructured":"Graham, R., Zang, N.: Enumerating split-pair arrangements. J. Combin. Theory, Series A\u00a0115(2), 293\u2013303 (2008)","journal-title":"J. Combin. Theory, Series A"},{"key":"18_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1007\/978-3-642-14455-4_41","volume-title":"Developments in Language Theory","author":"M.M. Halld\u00f3rsson","year":"2010","unstructured":"Halld\u00f3rsson, M.M., Kitaev, S., Pyatkin, A.: Graphs Capturing Alternations in Words. In: Gao, Y., Lu, H., Seki, S., Yu, S. (eds.) DLT 2010. LNCS, vol.\u00a06224, pp. 436\u2013437. Springer, Heidelberg (2010)"},{"key":"18_CR6","unstructured":"Hanen, C., Munier, A.: Cyclic scheduling on parallel processors: An overview. In: Chretienne, P., Coffman Jr., E.G., Lenstra, J.K., Liu, Z. (eds.) Scheduling Theory and its Applications, ch. 9, John Wiley & Sons (1995)"},{"key":"18_CR7","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1016\/j.endm.2007.07.084","volume":"29","author":"R. Hegde","year":"2007","unstructured":"Hegde, R., Jain, K.: The hardness of approximating poset dimension. Electronic Notes in Discrete Mathematics\u00a029, 435\u2013443 (2007)","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"18_CR8","first-page":"45","volume":"13","author":"S. Kitaev","year":"2008","unstructured":"Kitaev, S., Pyatkin, A.: On representable graphs. Automata, Languages and Combinatorics\u00a013, 45\u201354 (2008)","journal-title":"Automata, Languages and Combinatorics"},{"key":"18_CR9","doi-asserted-by":"crossref","unstructured":"Kitaev, S., Seif, S.: Word problem of the Perkins semigroup via directed acyclic graphs. Order (2008), doi: 10.1007\/s11083-008-9083-7","DOI":"10.1007\/s11083-008-9083-7"},{"key":"18_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/978-3-540-24595-7_6","volume-title":"Graph Drawing","author":"J. Kratochv\u00edl","year":"2004","unstructured":"Kratochv\u00edl, J., Pergel, M.: Two Results on Intersection Graphs of Polygons. In: Liotta, G. (ed.) GD 2003. LNCS, vol.\u00a02912, pp. 59\u201370. Springer, Heidelberg (2004)"},{"key":"18_CR11","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1002\/jos.95","volume":"5","author":"M. Middendorf","year":"2002","unstructured":"Middendorf, M., Timkovsky, V.G.: On scheduling cycle shops: Classification, complexity and approximation. Journal of Scheduling\u00a05, 135\u2013169 (2002)","journal-title":"Journal of Scheduling"},{"key":"18_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/978-3-540-74839-7_23","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M. Pergel","year":"2007","unstructured":"Pergel, M.: Recognition of Polygon-Circle Graphs And Graphs of Interval Filaments Is NP-Complete. In: Brandst\u00e4dt, A., Kratsch, D., M\u00fcller, H. (eds.) WG 2007. LNCS, vol.\u00a04769, pp. 238\u2013247. Springer, Heidelberg (2007)"},{"key":"18_CR13","unstructured":"Trotter, W.T.: Combinatorics and partially ordered sets: Dimension theory. Johns Hopkins Univ. Press (2001)"},{"issue":"3","key":"18_CR14","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1137\/0603036","volume":"3","author":"M. Yannakakis","year":"1982","unstructured":"Yannakakis, M.: The complexity of the partial order dimension problem. SIAM J. Algebraic Discrete Methods\u00a03(3), 351\u2013358 (1982)","journal-title":"SIAM J. Algebraic Discrete Methods"}],"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-25870-1_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,20]],"date-time":"2019-04-20T01:37:40Z","timestamp":1555724260000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-25870-1_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642258695","9783642258701"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-25870-1_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}