{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:30:21Z","timestamp":1725456621411},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642346101"},{"type":"electronic","value":"9783642346118"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-34611-8_9","type":"book-chapter","created":{"date-parts":[[2012,10,22]],"date-time":"2012-10-22T08:42:25Z","timestamp":1350895345000},"page":"57-68","source":"Crossref","is-referenced-by-count":0,"title":["The Maximum Clique Problem in Multiple Interval Graphs (Extended Abstract)"],"prefix":"10.1007","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","reference":[{"key":"9_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. Discrete and Computational Geometry\u00a019, 333\u2013334 (1998)","journal-title":"Discrete and Computational Geometry"},{"issue":"2","key":"9_CR2","doi-asserted-by":"publisher","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. Journal of Graph Algorithms and Applications\u00a016(2), 129\u2013150 (2012)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"9_CR3","unstructured":"Aumann, Y., Lewenstein, M., Melamud, O., Pinter, R.Y., Yakhini, Z.: Dotted interval graphs and high throughput genotyping. In: Proc. of the 16th Annual Symposium on Discrete Algorithms, SODA 2005, pp. 339\u2013348 (2005)"},{"key":"9_CR4","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.S., Shachnai, H., Shapira, I.: Scheduling split intervals. SIAM J. Comput.\u00a036, 1\u201315 (2006)","journal-title":"SIAM J. Comput."},{"key":"9_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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: Sack, J.-R., Akl, S.G., Dehne, F., Santoro, N. (eds.) WADS 1995. LNCS, vol.\u00a0955, pp. 449\u2013460. Springer, Heidelberg (1995)"},{"key":"9_CR6","unstructured":"Butman, A., Hermelin, D., Lewenstein, M., Rawitz, D.: Optimization problems in multiple-interval graphs. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, pp. 268\u2013277 (2007)"},{"key":"9_CR7","unstructured":"Cabello, S., Cardinal, J., Langerman, S.: The Clique Problem in Ray Intersection Graph. arXiv (November 2011), http:\/\/arxiv.org\/pdf\/1111.5986.pdf"},{"issue":"1","key":"9_CR8","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1137\/050629276","volume":"21","author":"M. Chleb\u00edk","year":"2007","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: The complexity of combinatorial optimization problems on d-dimensional boxes. SIAM Journal on Discrete Mathematics\u00a021(1), 158\u2013169 (2007)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"9_CR9","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":"9_CR10","doi-asserted-by":"publisher","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.\u00a06, 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"key":"9_CR11","doi-asserted-by":"publisher","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\u00a03, 261\u2013273 (1973)","journal-title":"Networks"},{"issue":"56","key":"9_CR12","doi-asserted-by":"publisher","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. Information Processing Letters\u00a073(56), 181\u2013188 (2000)","journal-title":"Information Processing Letters"},{"issue":"4","key":"9_CR13","doi-asserted-by":"publisher","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. Disc. Optimiz.\u00a03(4), 327\u2013340 (2006)","journal-title":"Disc. Optimiz."},{"issue":"1","key":"9_CR14","doi-asserted-by":"publisher","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.\u00a014(1), 224\u2013231 (1985)","journal-title":"SIAM J. Comput."},{"key":"9_CR15","unstructured":"Jiang, M.: Clique in 3-track interval graphs is APX-hard. arXiv (April 2012), http:\/\/arxiv.org\/pdf\/1204.2202v1.pdf"},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"Jiang, M., Zhang, Y.: Parameterized Complexity in Multiple-Interval Graphs: Domination, Partition, Separation, Irredundancy. arXiv (October 2011), http:\/\/arxiv.org\/pdf\/1110.0187v1.pdf","DOI":"10.1007\/978-3-642-22685-4_6"},{"key":"9_CR17","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/PL00009315","volume":"18","author":"T. Kaiser","year":"1997","unstructured":"Kaiser, T.: Transversals of d-Intervals. Discrete Comput. Geom.\u00a018, 195\u2013203 (1997)","journal-title":"Discrete Comput. Geom."},{"key":"9_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/978-3-642-15369-3_20","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"F. Kammer","year":"2010","unstructured":"Kammer, F., Tholey, T., Voepel, H.: Approximation Algorithms for Intersection Graphs. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX 2010, LNCS, vol.\u00a06302, pp. 260\u2013273. Springer, Heidelberg (2010)"},{"key":"9_CR19","unstructured":"K\u00f6nig, F.G.: Sorting with objectives. PhD thesis, Technische Universit\u00e4t Berlin (2009)"},{"key":"9_CR20","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. Commentationes Mathematicae Universitatis Carolinae\u00a031, 85\u201393 (1990)","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"9_CR21","doi-asserted-by":"publisher","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 Mathematics\u00a0108, 365\u2013372 (1992)","journal-title":"Discrete Mathematics"},{"key":"9_CR22","doi-asserted-by":"publisher","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. System Sci.\u00a043, 425\u2013440 (1991)","journal-title":"J. Comput. System Sci."},{"issue":"3","key":"9_CR23","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1002\/jgt.3190110317","volume":"11","author":"E.R. Scheinerman","year":"1987","unstructured":"Scheinerman, E.R.: The maximum interval number of graphs with given genus. Journal of Graph Theory\u00a011(3), 441\u2013446 (1987)","journal-title":"Journal of Graph Theory"},{"issue":"3","key":"9_CR24","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. Journal of Combinatorial Theory, Series B\u00a035(3), 224\u2013239 (1983)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"3","key":"9_CR25","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. Journal of Graph Theory\u00a03(3), 205\u2013211 (1979)","journal-title":"Journal of Graph Theory"},{"issue":"2","key":"9_CR26","doi-asserted-by":"publisher","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 Transactions on Computers\u00a030(2), 135\u2013140 (1981)","journal-title":"IEEE Transactions on Computers"},{"issue":"3","key":"9_CR27","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 Mathematics\u00a08(3), 295\u2013305 (1984)","journal-title":"Discrete Applied Mathematics"},{"key":"9_CR28","doi-asserted-by":"crossref","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proc. 38th ACM Symp. Theory of Computing, STOC 2006, pp. 681\u2013690 (2006)","DOI":"10.1145\/1132516.1132612"}],"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-642-34611-8_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,30]],"date-time":"2022-01-30T11:56:33Z","timestamp":1643543793000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-34611-8_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642346101","9783642346118"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-34611-8_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}