{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T02:04:39Z","timestamp":1725674679609},"publisher-location":"Berlin, Heidelberg","reference-count":52,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642293436"},{"type":"electronic","value":"9783642293443"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-29344-3_30","type":"book-chapter","created":{"date-parts":[[2012,4,10]],"date-time":"2012-04-10T14:19:29Z","timestamp":1334067569000},"page":"350-361","source":"Crossref","is-referenced-by-count":5,"title":["k-Gap Interval Graphs"],"prefix":"10.1007","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Serge","family":"Gaspers","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petr","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karol","family":"Suchan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik Jan","family":"van Leeuwen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Vatshelle","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yngve","family":"Villanger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"30_CR1","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/PL00009349","volume":"19","author":"N. Alon","year":"1998","unstructured":"Alon, N.: Piercing d-intervals. Discret. Comput. Geom.\u00a019(3), 333\u2013334 (1998)","journal-title":"Discret. Comput. Geom."},{"issue":"1","key":"30_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(86)90002-8","volume":"14","author":"T. Andreae","year":"1986","unstructured":"Andreae, T.: On an extremal problem concerning the interval number of a graph. Discrete Appl. Math.\u00a014(1), 1\u20139 (1986)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"30_CR3","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/0095-8956(89)90003-8","volume":"46","author":"T. Andreae","year":"1989","unstructured":"Andreae, T., Aigner, M.: The total interval number of a graph. J. Comb. Theory Ser. B\u00a046(1), 7\u201321 (1989)","journal-title":"J. Comb. Theory Ser. B"},{"unstructured":"Aumann, Y., Lewenstein, M., Melamud, O., Pinter, R.Y., Yakhini, Z.: Dotted interval graphs and high throughput genotyping. In: SODA 2005, pp. 339\u2013348 (2005)","key":"30_CR4"},{"issue":"1-3","key":"30_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 Appl. Math.\u00a071(1-3), 41\u201353 (1996)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"30_CR6","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1002\/jgt.20005","volume":"46","author":"J. Balogh","year":"2004","unstructured":"Balogh, J., Ochem, P., Pluh\u00e1r, A.: On the interval number of special graphs. J. Graph Theor.\u00a046(4), 241\u2013253 (2004)","journal-title":"J. Graph Theor."},{"issue":"1","key":"30_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539703437843","volume":"36","author":"R. Bar-Yehuda","year":"2006","unstructured":"Bar-Yehuda, R., Halld\u00f3rsson, M.M., Naor, J., Shachnai, H., Shapira, I.: Scheduling split intervals. SIAM J. Comput.\u00a036(1), 1\u201315 (2006)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"30_CR8","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/j.disopt.2006.05.010","volume":"3","author":"R. Bar-Yehuda","year":"2006","unstructured":"Bar-Yehuda, R., Rawitz, D.: Using fractional primal-dual to schedule split intervals with demands. Discrete Optim.\u00a03(4), 275\u2013287 (2006)","journal-title":"Discrete Optim."},{"key":"30_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-642-25870-1_6","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"R. Belmonte","year":"2011","unstructured":"Belmonte, R., Vatshelle, M.: Graph Classes with Structured Neighborhoods and Algorithmic Applications. In: Kolman, P., Kratochv\u00edl, J. (eds.) WG 2011. LNCS, vol.\u00a06986, pp. 47\u201358. Springer, Heidelberg (2011)"},{"unstructured":"Bessi\u00e8re, C., Hebrard, E., Hnich, B., Kiziltan, Z., Quimper, C.-G., Walsh, T.: The parameterized complexity of global constraints. In: AAAI 2008, pp. 235\u2013240 (2008)","key":"30_CR10"},{"issue":"1-3","key":"30_CR11","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/j.tcs.2007.07.002","volume":"385","author":"G. Blin","year":"2007","unstructured":"Blin, G., Fertin, G., Vialette, S.: Extracting constrained 2-interval subsets in 2-interval sets. Theor. Comput. Sci.\u00a0385(1-3), 241\u2013263 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"1-2","key":"30_CR12","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":"3","key":"30_CR13","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K.S. Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. J. Comput. System Sci.\u00a013(3), 335\u2013379 (1976)","journal-title":"J. Comput. System Sci."},{"issue":"39","key":"30_CR14","doi-asserted-by":"publisher","first-page":"5187","DOI":"10.1016\/j.tcs.2011.05.022","volume":"412","author":"B.-M. Bui-Xuan","year":"2011","unstructured":"Bui-Xuan, B.-M., Telle, J.A., Vatshelle, M.: Boolean-width of graphs. Theor. Comput. Sci.\u00a0412(39), 5187\u20135204 (2011)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Butman, A., Hermelin, D., Lewenstein, M., Rawitz, D.: Optimization problems in multiple-interval graphs. ACM Trans. Algorithms 6(2) (2010)","key":"30_CR15","DOI":"10.1145\/1721837.1721856"},{"issue":"2","key":"30_CR16","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1002\/jgt.3190160209","volume":"16","author":"P.A. Catlin","year":"1992","unstructured":"Catlin, P.A.: Supereulerian graphs: A survey. J. Graph Theor.\u00a016(2), 177\u2013196 (1992)","journal-title":"J. Graph Theor."},{"issue":"3","key":"30_CR17","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s10878-006-9030-8","volume":"13","author":"E. Chen","year":"2007","unstructured":"Chen, E., Yang, L., Yuan, H.: Improved algorithms for largest cardinality 2-interval pattern problem. J. Comb. Optim.\u00a013(3), 263\u2013275 (2007)","journal-title":"J. Comb. Optim."},{"key":"30_CR18","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/S0166-218X(01)00313-4","volume":"122","author":"M. Chen","year":"2002","unstructured":"Chen, M., Chang, G.J.: Total interval numbers of complete r-partite graphs. Discrete Appl. Math.\u00a0122, 83\u201392 (2002)","journal-title":"Discrete Appl. Math."},{"key":"30_CR19","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1051\/ita\/1992260302571","volume":"26","author":"B. Courcelle","year":"1992","unstructured":"Courcelle, B.: The monadic second-order logic of graphs III: tree-decompositions, minor and complexity issues. Rairo - Theor. Inform. Appl.\u00a026, 257\u2013286 (1992)","journal-title":"Rairo - Theor. Inform. Appl."},{"issue":"2-3","key":"30_CR20","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/j.tcs.2008.01.007","volume":"395","author":"M. Crochemore","year":"2008","unstructured":"Crochemore, M., Hermelin, D., Landau, G.M., Rawitz, D., Vialette, S.: Approximating the 2-interval pattern problem. Theor. Comput. Sci.\u00a0395(2-3), 283\u2013297 (2008)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. Springer (1999)","key":"30_CR21","DOI":"10.1007\/978-1-4612-0515-9"},{"issue":"2","key":"30_CR22","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0012-365X(85)90041-X","volume":"55","author":"P. Erd\u00f6s","year":"1985","unstructured":"Erd\u00f6s, P., West, D.B.: A note on the interval number of a graph. Discrete Math.\u00a055(2), 129\u2013133 (1985)","journal-title":"Discrete Math."},{"key":"30_CR23","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"M.R. Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci.\u00a0410, 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series XIV. Springer (2006)","key":"30_CR24"},{"doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Gaspers, S., Golovach, P., Suchan, K., Szeider, S., van Leeuwen, E.J., Vatshelle, M., Villanger, Y.: k-gap interval graphs. arXiv CoRR 1112.3244 (2011)","key":"30_CR25","DOI":"10.1007\/978-3-642-29344-3_30"},{"key":"30_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-540-74839-7_6","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"P. Gambette","year":"2007","unstructured":"Gambette, P., Vialette, S.: On Restrictions of Balanced 2-Interval Graphs. In: Brandst\u00e4dt, A., Kratsch, D., M\u00fcller, H. (eds.) WG 2007. LNCS, vol.\u00a04769, pp. 55\u201365. Springer, Heidelberg (2007)"},{"unstructured":"Gaspers, S., Szeider, S.: Kernels for global constraints. In: IJCAI 2011, pp. 540\u2013545 (2011)","key":"30_CR27"},{"doi-asserted-by":"crossref","unstructured":"Golumbic, M.C.: Algorithmic graph theory and perfect graphs. Academic Press (1980)","key":"30_CR28","DOI":"10.1016\/B978-0-12-289260-8.50010-8"},{"issue":"1","key":"30_CR29","doi-asserted-by":"publisher","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 J. Algebra. Discr.\u00a01(1), 1\u20137 (1980)","journal-title":"SIAM J. Algebra. Discr."},{"issue":"3","key":"30_CR30","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/j.orl.2007.11.002","volume":"36","author":"R. Hassin","year":"2008","unstructured":"Hassin, R., Segev, D.: Rounding to an integral program. Oper. Res. Lett.\u00a036(3), 321\u2013326 (2008)","journal-title":"Oper. Res. Lett."},{"key":"30_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/978-3-642-22953-4_8","volume-title":"Fundamentals of Computation Theory","author":"B.M.P. Jansen","year":"2011","unstructured":"Jansen, B.M.P., Kratsch, S.: Data Reduction for Graph Coloring Problems. In: Owe, O., Steffen, M., Telle, J.A. (eds.) FCT 2011. LNCS, vol.\u00a06914, pp. 90\u2013101. Springer, Heidelberg (2011)"},{"key":"30_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/978-3-642-28050-4_3","volume-title":"IPEC 2011","author":"M. Jiang","year":"2012","unstructured":"Jiang, M., Zhang, Y.: Parameterized Complexity in Multiple-interval Graphs: Domination. In: Rossmanith, P. (ed.) IPEC 2011. LNCS, vol.\u00a07112, pp. 27\u201340. Springer, Heidelberg (2012)"},{"key":"30_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/978-3-642-22685-4_6","volume-title":"Computing and Combinatorics","author":"M. Jiang","year":"2011","unstructured":"Jiang, M., Zhang, Y.: Parameterized Complexity in Multiple-Interval Graphs: Partition, Separation, Irredundancy. In: Fu, B., Du, D.-Z. (eds.) COCOON 2011. LNCS, vol.\u00a06842, pp. 62\u201373. Springer, Heidelberg (2011)"},{"doi-asserted-by":"crossref","unstructured":"Kaiser, T.: Transversals of d-intervals. Discret. Comput. Geom.\u00a018(2) (1997)","key":"30_CR34","DOI":"10.1007\/PL00009315"},{"key":"30_CR35","series-title":"LNCS","volume-title":"Treewidth, Computations and Approximations","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth, Computations and Approximations. LNCS, vol.\u00a0842. Springer, Heidelberg (1994)"},{"issue":"1","key":"30_CR36","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1002\/(SICI)1097-0118(199705)25:1<79::AID-JGT5>3.0.CO;2-F","volume":"25","author":"A.V. Kostochka","year":"1997","unstructured":"Kostochka, A.V., West, D.B.: Total interval number for graphs with bounded degree. J. Graph Theor.\u00a025(1), 79\u201384 (1997)","journal-title":"J. Graph Theor."},{"issue":"1-3","key":"30_CR37","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0012-365X(93)90057-Z","volume":"118","author":"T.M. Kratzke","year":"1993","unstructured":"Kratzke, T.M., West, D.B.: The total interval number of a graph, I: Fundamental classes. Discrete Math.\u00a0118(1-3), 145\u2013156 (1993)","journal-title":"Discrete Math."},{"issue":"2","key":"30_CR38","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1137\/S0895480193250162","volume":"9","author":"T.M. Kratzke","year":"1996","unstructured":"Kratzke, T.M., West, D.B.: The total interval number of a graph II: Trees and complexity. SIAM J. Discrete Math.\u00a09(2), 339\u2013348 (1996)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"30_CR39","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1016\/j.tcs.2005.10.008","volume":"351","author":"D. Marx","year":"2006","unstructured":"Marx, D.: Parameterized coloring problems on chordal graphs. Theor. Comput. Sci.\u00a0351(3), 407\u2013424 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"30_CR40","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1007\/s00453-008-9233-8","volume":"57","author":"D. Marx","year":"2010","unstructured":"Marx, D.: Chordal deletion is fixed-parameter tractable. Algorithmica\u00a057(4), 747\u2013768 (2010)","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press (2006)","key":"30_CR41","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"issue":"6","key":"30_CR42","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0020-0190(95)00163-8","volume":"56","author":"A. Raychaudhuri","year":"1995","unstructured":"Raychaudhuri, A.: The total interval number of a tree and the hamiltonian completion number of its line graph. Inform. Process. Lett.\u00a056(6), 299\u2013306 (1995)","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"30_CR43","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D.J. Rose","year":"1976","unstructured":"Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput.\u00a05(2), 266\u2013283 (1976)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"30_CR44","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1016\/0095-8956(83)90050-3","volume":"35","author":"E.R. Scheinerman","year":"1983","unstructured":"Scheinerman, E.R., West, D.B.: The interval number of a planar graph: Three intervals suffice. J. Comb. Theory Ser. B\u00a035(3), 224\u2013239 (1983)","journal-title":"J. Comb. Theory Ser. B"},{"doi-asserted-by":"crossref","unstructured":"Spinrad, J.P.: Efficient Graph Representations. Fields Institute Monographs, vol.\u00a019. AMS (2003)","key":"30_CR45","DOI":"10.1090\/fim\/019"},{"issue":"1","key":"30_CR46","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/BF01294464","volume":"15","author":"G. Tardos","year":"1995","unstructured":"Tardos, G.: Transversals of 2-intervals, a topological approach. Combinatorica\u00a015(1), 123\u2013134 (1995)","journal-title":"Combinatorica"},{"issue":"3","key":"30_CR47","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1002\/jgt.3190030302","volume":"3","author":"W.T. Trotter","year":"1979","unstructured":"Trotter, W.T., Harary, F.: On double and multiple interval graphs. J. Graph Theor.\u00a03(3), 205\u20132011 (1979)","journal-title":"J. Graph Theor."},{"issue":"3","key":"30_CR48","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/0206036","volume":"6","author":"S. Tsukiyama","year":"1977","unstructured":"Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput.\u00a06(3), 505\u2013517 (1977)","journal-title":"SIAM J. Comput."},{"issue":"2-3","key":"30_CR49","doi-asserted-by":"publisher","first-page":"224","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 problems. Theor. Comput. Sci.\u00a0312(2-3), 224\u2013239 (2004)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Vialette, S.: Two-interval pattern problems. In: Encyclopedia of Algorithms. Springer (2008)","key":"30_CR50","DOI":"10.1007\/978-0-387-30162-4_445"},{"issue":"3","key":"30_CR51","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0012-365X(89)90276-8","volume":"73","author":"D.B. West","year":"1989","unstructured":"West, D.B.: A short proof of the degree bound for interval number. Discrete Math.\u00a073(3), 309\u2013310 (1989)","journal-title":"Discrete Math."},{"key":"30_CR52","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 Appl. Math.\u00a08, 295\u2013305 (1984)","journal-title":"Discrete Appl. Math."}],"container-title":["Lecture Notes in Computer Science","LATIN 2012: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-29344-3_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,12]],"date-time":"2022-01-12T15:41:18Z","timestamp":1642002078000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-29344-3_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642293436","9783642293443"],"references-count":52,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-29344-3_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}