{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:46:08Z","timestamp":1725497168328},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540748380"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74839-7_6","type":"book-chapter","created":{"date-parts":[[2007,12,6]],"date-time":"2007-12-06T14:55:58Z","timestamp":1196952958000},"page":"55-65","source":"Crossref","is-referenced-by-count":6,"title":["On Restrictions of Balanced 2-Interval Graphs"],"prefix":"10.1007","author":[{"given":"Philippe","family":"Gambette","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"St\u00e9phane","family":"Vialette","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"6_CR1","unstructured":"Rebea, A.B.: \u00c9tude des stables dans les graphes quasi-adjoints. PhD thesis, Universit\u00e9 de Grenoble (1981)"},{"key":"6_CR2","series-title":"Lecture Notes in Computer Science","volume-title":"Combinatorial Pattern Matching","author":"G. Blin","year":"2004","unstructured":"Blin, G., Fertin, G., Vialette, S.: New results for the 2-interval pattern problem. In: Sahinalp, S.C., Muthukrishnan, S.M., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol.\u00a03109, Springer, Heidelberg (2004)"},{"key":"6_CR3","unstructured":"Butman, A., Hermelin, D., Lewenstein, M., Rawitz, D.: Optimization problems in multiple-interval graphs. In: Proceedings of SODA 2007, pp. 268\u2013277 (2007)"},{"key":"6_CR4","unstructured":"Brandst\u00e4dt, A., Le, V.B., Szymczak, T., Siegemund, F., de Ridder, H.N., Knorr, S., Rzehak, M., Mowitz, M., Ryabova, N.: ISGCI: Information System on Graph Class Inclusions. \n                  \n                    http:\/\/wwwteo.informatik.uni-rostock.de\/isgci\/classes.cgi"},{"issue":"1","key":"6_CR5","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0166-218X(96)00063-7","volume":"71","author":"V. Bafna","year":"1996","unstructured":"Bafna, V., Narayanan, B.O., Ravi, R.: Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles). Discrete Applied Math.\u00a071(1), 41\u201354 (1996)","journal-title":"Discrete Applied Math."},{"issue":"1","key":"6_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539703437843","volume":"36","author":"R. Bar-Yehuda","year":"2006","unstructured":"Bar-Yehuda, R., Halld\u00f3rson, M.M., Naor, J., Shachnai, H., Shapira, I.: Scheduling split intervals. SIAM Journal on Computing\u00a036(1), 1\u201315 (2006)","journal-title":"SIAM Journal on Computing"},{"key":"6_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/11561071_39","volume-title":"Algorithms \u2013 ESA 2005","author":"M. Crochemore","year":"2005","unstructured":"Crochemore, M., Hermelin, D., Landau, G.M., Vialette, S.: Approximating the 2-interval pattern problem. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 426\u2013437. Springer, Heidelberg (2005)"},{"key":"6_CR8","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0020-0190(95)00046-F","volume":"55","author":"D.G. Corneil","year":"1995","unstructured":"Corneil, D.G., Kim, H., Natarajan, S., Olariu, S., Sprague, A.P.: Simple linear time recognition of unit interval graphs. Information Processing Letters\u00a055, 99\u2013104 (1995)","journal-title":"Information Processing Letters"},{"key":"6_CR9","series-title":"London. Math. Soc. Lecture Notes","first-page":"153","volume-title":"Surveys in Combinatorics","author":"M. Chudnovsky","year":"2005","unstructured":"Chudnovsky, M., Seymour, P.: The structure of claw-free graphs. In: Surveys in Combinatorics. London. Math. Soc. Lecture Notes, vol.\u00a0327, pp. 153\u2013172. Cambridge University Press, Cambridge (2005)"},{"key":"6_CR10","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/S0012-365X(96)00045-3","volume":"164","author":"R. Faudree","year":"1997","unstructured":"Faudree, R., Flandrin, E., Ryj\u00e1\u010dek, Z.: Claw-free graphs - a survey. Discrete Mathematics\u00a0164, 87\u2013147 (1997)","journal-title":"Discrete Mathematics"},{"key":"6_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0601001","volume":"1","author":"J.R. Griggs","year":"1980","unstructured":"Griggs, J.R., West, D.B.: Extremal values of the interval number of a graph. SIAM Journal on Algebraic and Discrete Methods\u00a01, 1\u20137 (1980)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"6_CR12","first-page":"109","volume":"109","author":"A. Gy\u00e1rf\u00e1s","year":"1995","unstructured":"Gy\u00e1rf\u00e1s, A., West, D.B.: Multitrack interval graphs. Congress Numerantium\u00a0109, 109\u2013116 (1995)","journal-title":"Congress Numerantium"},{"key":"6_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/11917496_13","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M.M. Halld\u00f3rsson","year":"2006","unstructured":"Halld\u00f3rsson, M.M., Karlsson, R.K.: Strip graphs: Recognition and scheduling. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, pp. 137\u2013146. Springer, Heidelberg (2006)"},{"key":"6_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1007\/3-540-55706-7_29","volume-title":"Algorithm Theory - SWAT \u201992","author":"D. Joseph","year":"1992","unstructured":"Joseph, D., Meidanis, J., Tiwari, P.: Determining DNA sequence similarity using maximum independent set algorithms for interval graphs. In: Nurmi, O., Ukkonen, E. (eds.) SWAT 1992. LNCS, vol.\u00a0621, pp. 326\u2013337. Springer, Heidelberg (1992)"},{"key":"6_CR15","first-page":"85","volume-title":"Reducibility among combinatorial problems","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"6_CR16","unstructured":"Karlsson, R.: A survey of split intervals and related graphs, Manuscript (2005)"},{"key":"6_CR17","unstructured":"King, A., Reed, B.: Bounding \u03c7 in terms of \u03c9 ans \u03b4 for quasi-line graphs. Article in preparation (2007)"},{"key":"6_CR18","first-page":"5","volume":"139","author":"A.V. Kostochka","year":"1999","unstructured":"Kostochka, A.V., West, D.B.: Every outerplanar graph is the union of two interval graphs. Congress Numerantium\u00a0139, 5\u20138 (1999)","journal-title":"Congress Numerantium"},{"key":"6_CR19","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/0097-3165(78)90022-5","volume":"25","author":"L. Lov\u00e1sz","year":"1978","unstructured":"Lov\u00e1sz, L.: Kneser\u2019s conjecture, chromatic number, and homotopy. Journal of Combinatorial Theory Series A\u00a025, 319\u2013324 (1978)","journal-title":"Journal of Combinatorial Theory Series A"},{"key":"6_CR20","unstructured":"McGuigan, R.: Presentation at NSF-CBMS Conference at Colby College (1977)"},{"key":"6_CR21","unstructured":"Roberts, F.S.: Indifference graphs. In: Proof Techniques in Graph Theory, Proceedings of the Second Ann Arbor Graph Theory Conference, pp. 139\u2013146 (1969)"},{"key":"6_CR22","unstructured":"Vialette, S.: Aspects algorithmiques de la pr\u00e9diction des structures secondaires d\u2019ARN. PhD thesis, Universit\u00e9 Paris 7 (2001)"},{"issue":"2-3","key":"6_CR23","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/j.tcs.2003.08.010","volume":"312","author":"S. Vialette","year":"2004","unstructured":"Vialette, S.: On the computational complexity of 2-interval pattern matching. Theoretical Computer Science\u00a0312(2-3), 223\u2013249 (2004)","journal-title":"Theoretical Computer Science"},{"key":"6_CR24","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0166-218X(84)90127-6","volume":"8","author":"D.B. West","year":"1984","unstructured":"West, D.B., Shmoys, D.B.: Recognizing graphs with fixed interval number is NP-complete. Discrete Applied Math.\u00a08, 295\u2013305 (1984)","journal-title":"Discrete Applied Math."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74839-7_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:42:37Z","timestamp":1619520157000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74839-7_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540748380"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74839-7_6","relation":{},"subject":[]}}