{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T05:51:00Z","timestamp":1761630660829},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2013,9,11]],"date-time":"2013-09-11T00:00:00Z","timestamp":1378857600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,4]]},"DOI":"10.1007\/s00453-013-9828-6","type":"journal-article","created":{"date-parts":[[2013,9,11]],"date-time":"2013-09-11T08:25:06Z","timestamp":1378887906000},"page":"812-836","source":"Crossref","is-referenced-by-count":13,"title":["The Maximum Clique Problem in Multiple Interval Graphs"],"prefix":"10.1007","volume":"71","author":[{"given":"Mathew C.","family":"Francis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Gon\u00e7alves","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Ochem","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,9,11]]},"reference":[{"issue":"2","key":"9828_CR1","doi-asserted-by":"crossref","first-page":"129","DOI":"10.7155\/jgaa.00253","volume":"16","author":"A. Asinowski","year":"2012","unstructured":"Asinowski, A., Cohen, E., Golumbic, M.C., Limouzy, V., Lipshteyn, M., Stern, M.: Vertex intersection graphs of paths on a grid. J. Graph Algorithms Appl. 16(2), 129\u2013150 (2012)","journal-title":"J. Graph Algorithms Appl."},{"key":"9828_CR2","first-page":"339","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201905","author":"Y. Aumann","year":"2005","unstructured":"Aumann, Y., Lewenstein, M., Melamud, O., Pinter, R.Y., Yakhini, Z.: Dotted interval graphs and high throughput genotyping. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201905, pp. 339\u2013348. Society for Industrial and Applied Mathematics, Philadelphia (2005)"},{"key":"9828_CR3","doi-asserted-by":"crossref","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.S., Shachnai, H., Shapira, I.: Scheduling split intervals. SIAM J. Comput. 36, 1\u201315 (2006)","journal-title":"SIAM J. Comput."},{"key":"9828_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/3-540-60220-8_84","volume-title":"Algorithms and Data Structures","author":"P. Berman","year":"1995","unstructured":"Berman, P., Fujito, T.: On approximation properties of the independent set problem for degree 3 graphs. In: Algorithms and Data Structures. Lecture Notes in Computer Science, vol. 955, pp. 449\u2013460. Springer, Berlin (1995)"},{"key":"9828_CR5","first-page":"268","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201907","author":"A. Butman","year":"2007","unstructured":"Butman, A., Hermelin, D., Lewenstein, M., Rawitz, D.: Optimization problems in multiple-interval graphs. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201907, pp. 268\u2013277. Society for Industrial and Applied Mathematics, Philadelphia (2007)"},{"key":"9828_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/978-3-642-33090-2_22","volume-title":"Algorithms\u2014ESA 2012","author":"S. Cabello","year":"2012","unstructured":"Cabello, S., Cardinal, J., Langerman, S.: The clique problem in ray intersection graphs. In: Algorithms\u2014ESA 2012. Lecture Notes in Computer Science, vol. 7501, pp. 241\u2013252. Springer, Berlin (2012)"},{"issue":"1","key":"9828_CR7","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1137\/050629276","volume":"21","author":"M. Chleb\u00edk","year":"2007","unstructured":"Chleb\u00edk, M., Chleb\u00edkova, J.: The complexity of combinatorial optimization problems on d-dimensional boxes. SIAM J. Discrete Math. 21(1), 158\u2013169 (2007)","journal-title":"SIAM J. Discrete Math."},{"key":"9828_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1007\/11561071_39","volume-title":"Algorithms\u2014ESA 2005","author":"M. Crochemore","year":"2005","unstructured":"Crochemore, M., Hermelin, D., Landau, G.M., Vialette, S.: Approximating the 2-interval pattern problem. In: Algorithms\u2014ESA 2005. Lecture Notes in Computer Science, vol. 3669, pp. 426\u2013437. Springer, Berlin (2005)"},{"key":"9828_CR9","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"M. Fellows","year":"2009","unstructured":"Fellows, M., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410, 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9828_CR10","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1137\/0132071","volume":"6","author":"M.R. Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: Rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 6, 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"key":"9828_CR11","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1002\/net.3230030305","volume":"3","author":"F. Gavril","year":"1973","unstructured":"Gavril, F.: Algorithms for a maximum clique and a maximum independent set of a circle graph. Networks 3, 261\u2013273 (1973)","journal-title":"Networks"},{"issue":"5\u20136","key":"9828_CR12","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0020-0190(00)00025-9","volume":"73","author":"F. Gavril","year":"2000","unstructured":"Gavril, F.: Maximum weight independent sets and cliques in intersection graphs of filaments. Inf. Process. Lett. 73(5\u20136), 181\u2013188 (2000)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"9828_CR13","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/j.disopt.2006.02.002","volume":"3","author":"D.S. Hochbaum","year":"2006","unstructured":"Hochbaum, D.S., Levin, A.: Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms. Discrete Optim. 3(4), 327\u2013340 (2006)","journal-title":"Discrete Optim."},{"issue":"1","key":"9828_CR14","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1137\/0214018","volume":"14","author":"W.L. Hsu","year":"1985","unstructured":"Hsu, W.L.: Maximum weight clique algorithms for circular-arc graphs and circle graphs. SIAM J. Comput. 14(1), 224\u2013231 (1985)","journal-title":"SIAM J. Comput."},{"key":"9828_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/978-3-642-13509-5_12","volume-title":"Proceedings of CPM 2010","author":"M. Jiang","year":"2010","unstructured":"Jiang, M.: On the parameterized complexity of some optimization problems related to multiple-interval graphs. In: Proceedings of CPM 2010. Lecture Notes in Computer Science, vol. 6129, pp. 125\u2013137. Springer, Berlin (2010)"},{"key":"9828_CR16","unstructured":"Jiang, M.: Clique in 3-track interval graphs is APX-hard (2012). arXiv:1204.2202 [cs.CC]"},{"key":"9828_CR17","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.tcs.2012.01.025","volume":"461","author":"M. Jiang","year":"2012","unstructured":"Jiang, M., Zhang, Y.: Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy. Theor. Comput. Sci. 461, 27\u201344 (2012). doi: 10.1016\/j.tcs.2012.01.025","journal-title":"Theor. Comput. Sci."},{"key":"9828_CR18","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/PL00009315","volume":"18","author":"T. Kaiser","year":"1997","unstructured":"Kaiser, T.: Transversals of d-intervals. Discrete Comput. Geom. 18, 195\u2013203 (1997)","journal-title":"Discrete Comput. Geom."},{"key":"9828_CR19","author":"F. Kammer","year":"2012","unstructured":"Kammer, F., Tholey, T.: Approximation algorithms for intersection graphs. Algorithmica (2012). doi: 10.1007\/s00453-012-9671-1","journal-title":"Algorithmica"},{"key":"9828_CR20","unstructured":"K\u00f6nig, F.G.: Sorting with objectives. Ph.D. thesis, Technische Universit\u00e4t Berlin (2009)"},{"issue":"1","key":"9828_CR21","first-page":"85","volume":"31","author":"J. Kratochv\u00edl","year":"1990","unstructured":"Kratochv\u00edl, J., Ne\u0161et\u0159il, J.: INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs. Comment. Math. Univ. Carol. 31(1), 85\u201393 (1990)","journal-title":"Comment. Math. Univ. Carol."},{"key":"9828_CR22","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/0012-365X(92)90688-C","volume":"108","author":"M. Middendorf","year":"1992","unstructured":"Middendorf, M., Pfeiffer, F.: The max clique problem in classes of string-graphs. Discrete Math. 108, 365\u2013372 (1992)","journal-title":"Discrete Math."},{"key":"9828_CR23","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/BF00290149","volume":"22","author":"B. Monien","year":"1985","unstructured":"Monien, B., Speckenmeyer, E.: Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Inform. 22, 115\u2013123 (1985)","journal-title":"Acta Inform."},{"issue":"3","key":"9828_CR24","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9828_CR25","doi-asserted-by":"crossref","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 Theory 3(3), 205\u2013211 (1979)","journal-title":"J. Graph Theory"},{"issue":"2","key":"9828_CR26","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1109\/TC.1981.6312176","volume":"30","author":"L.G. Valiant","year":"1981","unstructured":"Valiant, L.G.: Universality considerations in VLSI circuits. IEEE Trans. Comput. 30(2), 135\u2013140 (1981)","journal-title":"IEEE Trans. Comput."},{"issue":"3","key":"9828_CR27","doi-asserted-by":"crossref","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. 8(3), 295\u2013305 (1984)","journal-title":"Discrete Appl. Math."},{"key":"9828_CR28","first-page":"681","volume-title":"Proceedings of the 38th ACM Symposium on Theory of Computing, STOC \u201906","author":"D. Zuckerman","year":"2006","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of the 38th ACM Symposium on Theory of Computing, STOC \u201906, pp. 681\u2013690. ACM, New York (2006)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9828-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9828-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9828-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:12Z","timestamp":1559137512000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9828-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9,11]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,4]]}},"alternative-id":["9828"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9828-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9,11]]}}}