{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T01:12:58Z","timestamp":1768439578732,"version":"3.49.0"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,7,4]],"date-time":"2012-07-04T00:00:00Z","timestamp":1341360000000},"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":[[2014,2]]},"DOI":"10.1007\/s00453-012-9671-1","type":"journal-article","created":{"date-parts":[[2012,7,3]],"date-time":"2012-07-03T17:32:29Z","timestamp":1341336749000},"page":"312-336","source":"Crossref","is-referenced-by-count":21,"title":["Approximation Algorithms for Intersection Graphs"],"prefix":"10.1007","volume":"68","author":[{"given":"Frank","family":"Kammer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Torsten","family":"Tholey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,7,4]]},"reference":[{"key":"9671_CR1","series-title":"Applied Optimization","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1007\/978-1-4757-3613-7_23","volume-title":"Computational Methods in Decision-Making, Economics and Finance","author":"K. Akcoglu","year":"2002","unstructured":"Akcoglu, K., Aspnes, J., DasGupta, B., Kao, M.-Y.: Opportunity cost algorithms for combinatorial auctions. In: Kontoghiorghes, E.J., Rustem, B., Siokos, S. (eds.) Computational Methods in Decision-Making, Economics and Finance. Applied Optimization, vol. 74, pp. 455\u2013479. Kluwer Academic, Dordrecht (2002)"},{"key":"9671_CR2","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., Shachnai, H., Shapira, I.: Scheduling split intervals. SIAM J. Comput. 36, 1\u201315 (2006)","journal-title":"SIAM J. Comput."},{"key":"9671_CR3","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"9671_CR4","doi-asserted-by":"crossref","DOI":"10.1145\/1721837.1721856","volume":"6","author":"A. Butman","year":"2010","unstructured":"Butman, A., Hermelin, D., Lewenstein, M., Rawitz, D.: Optimization problems in multiple-interval graphs. ACM Trans. Algorithms 6, Article\u00a040 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"9671_CR5","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/j.endm.2004.06.012","volume":"18","author":"M.R. Cerioli","year":"2004","unstructured":"Cerioli, M.R., Faria, L., Ferreira, T.O., Protti, F.: On minimum clique partition and maximum independent set on unit disk graphs and penny graphs: complexity and approximation. Electron. Notes Discrete Math. 18, 73\u201379 (2004)","journal-title":"Electron. Notes Discrete Math."},{"key":"9671_CR6","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1016\/S0196-6774(02)00294-8","volume":"46","author":"T.M. Chan","year":"2003","unstructured":"Chan, T.M.: Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms 46, 178\u2013189 (2003)","journal-title":"J. Algorithms"},{"key":"9671_CR7","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"B.N. Clark","year":"1990","unstructured":"Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Math. 86, 165\u2013177 (1990)","journal-title":"Discrete Math."},{"key":"9671_CR8","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85, 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"9671_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)"},{"key":"9671_CR10","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/s00373-011-1026-1","volume":"27","author":"A. Dumitrescu","year":"2011","unstructured":"Dumitrescu, A., Pach, J.: Minimum clique partition in unit disk graphs. Graphs Comb. 27, 399\u2013411 (2011)","journal-title":"Graphs Comb."},{"key":"9671_CR11","doi-asserted-by":"crossref","first-page":"1302","DOI":"10.1137\/S0097539702402676","volume":"34","author":"T. Erlebach","year":"2005","unstructured":"Erlebach, T., Jansen, K., Seidel, E.: Polynomial-time approximation schemes for geometric intersection graphs. SIAM J. Comput. 34, 1302\u20131323 (2005)","journal-title":"SIAM J. Comput."},{"key":"9671_CR12","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"747","DOI":"10.1007\/978-3-540-78773-0_64","volume-title":"Proc. 8th Latin American Theoretical Informatics Symposium (LATIN 2008)","author":"T. Erlebach","year":"2008","unstructured":"Erlebach, T., van Leeuwen, E.J.: Domination in geometric intersection graphs. In: Proc. 8th Latin American Theoretical Informatics Symposium (LATIN 2008). LNCS, vol. 4957, pp. 747\u2013758. Springer, Berlin (2008)"},{"key":"9671_CR13","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/BF01196133","volume":"17","author":"U. Feige","year":"1997","unstructured":"Feige, U.: Randomized graph products, chromatic numbers, and the Lov\u00e1sz \u03d1 function. Combinatorica 17, 79\u201390 (1997)","journal-title":"Combinatorica"},{"key":"9671_CR14","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"9671_CR15","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"12","author":"R.J. Fowler","year":"1981","unstructured":"Fowler, R.J., Paterson, M.S., Tanimoto, S.L.: Optimal packing and covering in the plane are NP-complete. Inf. Process. Lett. 12, 133\u2013137 (1981)","journal-title":"Inf. Process. Lett."},{"key":"9671_CR16","series-title":"Congr. Numer","first-page":"211","volume-title":"Proc. 5th British Combinatorial Conference","author":"A. Frank","year":"1976","unstructured":"Frank, A.: Some polynomial algorithms for certain graphs and hypergraphs. In: Proc. 5th British Combinatorial Conference, Aberdeen, 1975. Congr. Numer, vol. 15, pp. 211\u2013226 (1976)"},{"key":"9671_CR17","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1, 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"key":"9671_CR18","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F. Gavril","year":"1972","unstructured":"Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comput. 1, 180\u2013187 (1972)","journal-title":"SIAM J. Comput."},{"key":"9671_CR19","series-title":"LNCS","first-page":"243","volume-title":"Proc. 18th Annual European Symposium on Algorithms (ESA 2010)","author":"M. Gibson","year":"2010","unstructured":"Gibson, M., Pirwani, I.A.: Algorithms for dominating set in disk graphs: breaking the logn barrier. In: Proc. 18th Annual European Symposium on Algorithms (ESA 2010). LNCS, vol. 6346, pp. 243\u2013254. Springer, Berlin (2010)"},{"key":"9671_CR20","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)"},{"key":"9671_CR21","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/BF01864170","volume":"4","author":"M.C. Golumbic","year":"1988","unstructured":"Golumbic, M.C.: Algorithmic aspects of intersection graphs and representation hypergraphs. Graphs Comb. 4, 307\u2013321 (1988)","journal-title":"Graphs Comb."},{"key":"9671_CR22","unstructured":"Gr\u00e4f, A.: Coloring and recognizing special graph classes. PhD thesis, Technical Report Musikinformatik und Medientechnik Bericht 20\/95, Johannes Gutenberg-Universit\u00e4t Mainz (1995)"},{"key":"9671_CR23","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 J. Algebr. Discrete Methods 1, 1\u20137 (1980)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"9671_CR24","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1145\/1989493.1989520","volume-title":"Proc. 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 11)","author":"M. Hoefer","year":"2011","unstructured":"Hoefer, M., Kesselheim, T., V\u00f6cking, B.: Approximation algorithms for secondary spectrum auctions. In: Proc. 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 11), pp. 177\u2013186 (2011)"},{"key":"9671_CR25","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1006\/jagm.1997.0903","volume":"26","author":"H.B. Hunt III","year":"1998","unstructured":"Hunt, H.B. III, Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. J. Algorithms 26, 238\u2013274 (1998)","journal-title":"J. Algorithms"},{"key":"9671_CR26","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/j.ipl.2008.09.021","volume":"109","author":"J.L. Hurink","year":"2008","unstructured":"Hurink, J.L., Nieberg, T.: Approximating minimum independent dominating sets in wireless networks. Inf. Process. Lett. 109, 155\u2013160 (2008)","journal-title":"Inf. Process. Lett."},{"key":"9671_CR27","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1016\/0196-6774(83)90012-3","volume":"4","author":"H. Imai","year":"1983","unstructured":"Imai, H., Asano, T.: Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane. J. Algorithms 4, 310\u2013323 (1983)","journal-title":"J. Algorithms"},{"key":"9671_CR28","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/S0012-365X(99)00231-9","volume":"215","author":"R.E. Jamison","year":"2000","unstructured":"Jamison, R.E., Mulder, H.M.: Tolerance intersection graphs on binary trees with constant tolerance 3. Discrete Math. 215, 115\u2013131 (2000)","journal-title":"Discrete Math."},{"key":"9671_CR29","series-title":"LNCS","first-page":"62","volume-title":"Proc. 17th International Computing & Combinatorics Conference (COCOON 2011)","author":"M. Jiang","year":"2011","unstructured":"Jiang, M., Zhang, Y.: Parameterized complexity in multiple-interval graphs: partition, separation, irredundancy. In: Proc. 17th International Computing & Combinatorics Conference (COCOON 2011). LNCS, vol. 6842, pp. 62\u201373. Springer, Berlin (2011)"},{"key":"9671_CR30","unstructured":"Kammer, F., Tholey, T., Voepel, H.: Approximation algorithms for intersection graphs. Report 2009-6, Institut f\u00fcr Informatik, Universit\u00e4t Augsburg (2009)"},{"key":"9671_CR31","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1007\/978-3-642-15369-3_20","volume-title":"Proc. 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2010) and 14th International Workshop on Randomization and Computation (RANDOM 2010)","author":"F. Kammer","year":"2010","unstructured":"Kammer, F., Tholey, T., Voepel, H.: Approximation algorithms for intersection graphs. In: Proc. 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2010) and 14th International Workshop on Randomization and Computation (RANDOM 2010). LNCS, vol. 6302, pp. 260\u2013273. Springer, Berlin (2010)"},{"key":"9671_CR32","unstructured":"Malesi\u0144ska, E.: Graph-theoretical models for frequency assignment problems. PhD thesis, University of Berlin (1997)"},{"key":"9671_CR33","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/net.3230250205","volume":"25","author":"M.V. Marathe","year":"1995","unstructured":"Marathe, M.V., Breu, H., Hunt, H.B. III, Ravi, S.S., Rosenkrantz, D.J.: Simple heuristics for unit disk graphs. Networks 25, 59\u201368 (1995)","journal-title":"Networks"},{"key":"9671_CR34","doi-asserted-by":"crossref","DOI":"10.1145\/1383369.1383380","volume":"4","author":"T. Nieberg","year":"2008","unstructured":"Nieberg, T., Hurink, J., Kern, W.: Approximation schemes for wireless networks. ACM Trans. Algorithms 4, Article\u00a049 (2008)","journal-title":"ACM Trans. Algorithms"},{"key":"9671_CR35","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, New York (2006)"},{"key":"9671_CR36","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, 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"9671_CR37","series-title":"LNCS","first-page":"188","volume-title":"Proc. 12th Scandinavian Symposium and Workshops on Algorithms Theory (SWAT 2010)","author":"I.A. Pirwani","year":"2010","unstructured":"Pirwani, I.A., Salavatipour, M.R.: A weakly robust PTAS for minimum clique partition in unit disk graphs. In: Proc. 12th Scandinavian Symposium and Workshops on Algorithms Theory (SWAT 2010). LNCS, vol. 6139, pp. 188\u2013199. Springer, Berlin (2010). Full version to appear in Algorithmica"},{"key":"9671_CR38","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1145\/800116.803775","volume-title":"Proc. 7th Annual ACM Symposium on Theory of Computing (STOC 1975)","author":"D.J. Rose","year":"1975","unstructured":"Rose, D.J., Tarjan, R.E.: Algorithmic aspects of vertex elimination. In: Proc. 7th Annual ACM Symposium on Theory of Computing (STOC 1975), pp. 245\u2013254 (1975)"},{"key":"9671_CR39","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1287\/opre.34.2.250","volume":"34","author":"\u00c9. Tardos","year":"1986","unstructured":"Tardos, \u00c9.: A strongly polynomial algorithm to solve combinatorial linear programs. Oper. Res. 34, 250\u2013256 (1986)","journal-title":"Oper. Res."},{"key":"9671_CR40","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"774","DOI":"10.1007\/978-3-642-02927-1_64","volume-title":"36th International Colloquium on Automata, Languages and Programming (ICALP 2009)","author":"Y. Ye","year":"2009","unstructured":"Ye, Y., Borodin, A.: Elimination graphs. In: 36th International Colloquium on Automata, Languages and Programming (ICALP 2009). LNCS, vol. 5555, pp. 774\u2013785. Springer, Berlin (2009)"},{"key":"9671_CR41","doi-asserted-by":"crossref","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D. Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3, 103\u2013128 (2007)","journal-title":"Theory Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9671-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9671-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9671-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:10Z","timestamp":1559137510000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9671-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7,4]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["9671"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9671-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,7,4]]}}}