{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:47:28Z","timestamp":1725558448976},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642137303"},{"type":"electronic","value":"9783642137310"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13731-0_32","type":"book-chapter","created":{"date-parts":[[2010,6,10]],"date-time":"2010-06-10T07:00:50Z","timestamp":1276153250000},"page":"334-345","source":"Crossref","is-referenced-by-count":4,"title":["Fixed-Parameter Algorithms for Cochromatic Number and Disjoint Rectangle Stabbing"],"prefix":"10.1007","author":[{"given":"Pinar","family":"Heggernes","sequence":"first","affiliation":[]},{"given":"Dieter","family":"Kratsch","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"32_CR1","unstructured":"Berge, C.: F\u00e4rbung von Graphen, deren s\u00e4mtliche bzw. deren ungeraden Kreise starr sind (Zusammenfassung), Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur., Reihe 10, \u00a0114 (1961)"},{"key":"32_CR2","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0012-365X(94)00296-U","volume":"152","author":"A. Brandst\u00e4dt","year":"1996","unstructured":"Brandst\u00e4dt, A.: Partitions of graphs into one or two independent sets and cliques. Discrete Mathematics\u00a0152, 47\u201354 (1996)","journal-title":"Discrete Mathematics"},{"key":"32_CR3","first-page":"263","volume":"22","author":"A. Brandst\u00e4dt","year":"1986","unstructured":"Brandst\u00e4dt, A., Kratsch, D.: On the partition of permutations into increasing or decreasing subsequences. Elektron. Inform. Kybernet.\u00a022, 263\u2013273 (1986)","journal-title":"Elektron. Inform. Kybernet."},{"key":"32_CR4","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM, Philadelphia (1999)"},{"key":"32_CR5","doi-asserted-by":"crossref","unstructured":"Chen, J., Liu, Y., Lu, S., O\u2019Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM\u00a055 (2008)","DOI":"10.1145\/1374376.1374404"},{"key":"32_CR6","doi-asserted-by":"publisher","first-page":"1188","DOI":"10.1016\/j.jcss.2008.05.002","volume":"74","author":"J. Chen","year":"2008","unstructured":"Chen, J., Fomin, F.V., Liu, Y., Lu, S., Villanger, Y.: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci.\u00a074, 1188\u20131198 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"32_CR7","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s00493-005-0012-8","volume":"25","author":"M. Chudnovsky","year":"2005","unstructured":"Chudnovsky, M., Cornuejols, G., Liu, X., Seymour, P., Vuskovic, K.: Recognizing berge graphs. Combinatorica\u00a025, 143\u2013186 (2005)","journal-title":"Combinatorica"},{"key":"32_CR8","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1006\/jagm.2002.1221","volume":"43","author":"T.I.D.R. Gaur","year":"2002","unstructured":"Gaur, T.I.D.R., Krishnamurti, R.: Constant ratio approximation algorithms for the rectangle stabbing problem and the rectilinear partitioning problem. Journal of Algorithms\u00a043, 138\u2013152 (2002)","journal-title":"Journal of Algorithms"},{"key":"32_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/978-3-540-28639-4_24","volume-title":"Parameterized and Exact Computation","author":"F.K.H.A. Dehne","year":"2004","unstructured":"Dehne, F.K.H.A., Fellows, M.R., Rosamond, F.A., Shaw, P.: Greedy localization, iterative compression, modeled crown reductions: New FPT techniques, an improved algorithm for set splitting, and a novel 2k kernelization for vertex cover. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol.\u00a03162, pp. 271\u2013280. Springer, Heidelberg (2004)"},{"key":"32_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1007\/978-3-642-00202-1_26","volume-title":"WALCOM: Algorithms and Computation","author":"M. Dom","year":"2009","unstructured":"Dom, M., Fellows, M.R., Rosamond, F.A.: Parameterized complexity of stabbing rectangles and squares in the plane. In: Das, S., Uehara, R. (eds.) WALCOM 2009. LNCS, vol.\u00a05431, pp. 298\u2013309. Springer, Heidelberg (2009)"},{"key":"32_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/978-3-540-69311-6_30","volume-title":"Frontiers in Algorithmics","author":"M. Dom","year":"2008","unstructured":"Dom, M., Sikdar, S.: The parameterized complexity of the rectangle stabbing problem and its variants. In: Preparata, F.P., Wu, X., Yin, J. (eds.) FAW 2008. LNCS, vol.\u00a05059, pp. 288\u2013299. Springer, Heidelberg (2008)"},{"key":"32_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.D. Downey","year":"1999","unstructured":"Downey, R.D., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"32_CR13","first-page":"261","volume-title":"Quo Vadis, Graph Theory?","author":"P. Erd\u0151s","year":"1993","unstructured":"Erd\u0151s, P., Gimbel, J.: Some problems and results in cochromatic theory. In: Quo Vadis, Graph Theory?, pp. 261\u2013264. North-Holland, Amsterdam (1993)"},{"key":"32_CR14","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1002\/jgt.3190150604","volume":"15","author":"P. Erd\u0151s","year":"1991","unstructured":"Erd\u0151s, P., Gimbel, J., Kratsch, D.: Extremal results in cochromatic and dichromatic theory. Journal of Graph Theory\u00a015, 579\u2013585 (1991)","journal-title":"Journal of Graph Theory"},{"key":"32_CR15","first-page":"463","volume":"2","author":"P. Erd\u0151s","year":"1935","unstructured":"Erd\u0151s, P., Szekeres, G.: A combinatorial problem in geometry. Compositio Mathematica\u00a02, 463\u2013470 (1935)","journal-title":"Compositio Mathematica"},{"key":"32_CR16","volume-title":"Interval Orders and Interval Graphs: A Study of Partially Ordered Sets","author":"P.C. Fishburn","year":"1985","unstructured":"Fishburn, P.C.: Interval Orders and Interval Graphs: A Study of Partially Ordered Sets. Wiley, Chichester (1985)"},{"key":"32_CR17","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"32_CR18","unstructured":"Fomin, F.V., Iwama, K., Kratsch, D., Kaski, P., Koivisto, M., Kowalik, L., Okamoto, Y., van Rooij, J., Williams, R.: 08431 Open problems \u2013 moderately exponential time algorithms. In: Fomin, F.V., Iwama, K., Kratsch, D. (eds.) Moderately Exponential Time Algorithms, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany. Dagstuhl Seminar Proceedings, vol.\u00a008431 (2008)"},{"key":"32_CR19","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/S0020-0190(02)00288-0","volume":"84","author":"F.V. Fomin","year":"2002","unstructured":"Fomin, F.V., Kratsch, D., Novelli, J.-C.: Approximating minimum cocolorings. Inf. Process. Lett.\u00a084, 285\u2013290 (2002)","journal-title":"Inf. Process. Lett."},{"key":"32_CR20","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1016\/0095-8956(80)90079-9","volume":"29","author":"A. Frank","year":"1980","unstructured":"Frank, A.: On chain and antichain families of a partially ordered set. J. Comb. Theory, Ser. B\u00a029, 176\u2013184 (1980)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"32_CR21","unstructured":"Giannopoulos, P., Knauer, C., Rote, G., Werner, D.: Fixed-parameter tractability and lower bounds for stabbing problems. In: Proceedings of the 25th European Workshop on Computational Geometry (EuroCG), pp. 281\u2013284 (2009)"},{"key":"32_CR22","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, 2nd edn., vol.\u00a057. Elsevier, Amsterdam (2004)","edition":"2"},{"key":"32_CR23","first-page":"325","volume":"21","author":"M. Gr\u00f6tschel","year":"1984","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Polynomial algorithms for perfect graph. Annals of Discrete Mathematics\u00a021, 325\u2013356 (1984)","journal-title":"Annals of Discrete Mathematics"},{"key":"32_CR24","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0166-218X(91)90011-K","volume":"30","author":"R. Hassin","year":"1991","unstructured":"Hassin, R., Megiddo, N.: Approximation algorithms for hitting objects with straight lines. Discrete Applied Mathematics\u00a030, 29\u201342 (1991)","journal-title":"Discrete Applied Mathematics"},{"key":"32_CR25","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/j.jalgor.2003.07.001","volume":"50","author":"W. Jia","year":"2004","unstructured":"Jia, W., Zhang, C., Chen, J.: An efficient parameterized algorithm for -set packing. J. Algorithms\u00a050, 106\u2013117 (2004)","journal-title":"J. Algorithms"},{"key":"32_CR26","doi-asserted-by":"publisher","first-page":"748","DOI":"10.1137\/S089548010444273X","volume":"20","author":"S. Kovaleva","year":"2006","unstructured":"Kovaleva, S., Spieksma, F.C.R.: Approximation algorithms for rectangles tabbing and interval stabbing problems. SIAM J. Discrete Mathematics\u00a020, 748\u2013768 (2006)","journal-title":"SIAM J. Discrete Mathematics"},{"key":"32_CR27","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0095-8956(72)90045-7","volume":"13","author":"L. Lov\u00e1sz","year":"1972","unstructured":"Lov\u00e1sz, L.: A characterization of perfect graphs. J. Comb. Theory, Ser. B\u00a013, 95\u201398 (1972)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"32_CR28","volume-title":"Threshold graphs and related topics","author":"N. Mahadev","year":"1995","unstructured":"Mahadev, N., Peled, U.: Threshold graphs and related topics, vol.\u00a056. North-Holland, Amsterdam (1995)"},{"key":"32_CR29","series-title":"Oxford Lecture Series in Mathematics and Its Applications","doi-asserted-by":"publisher","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 Lecture Series in Mathematics and Its Applications. Oxford University Press, USA (2006)"},{"key":"32_CR30","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"B.A. Reed","year":"2004","unstructured":"Reed, B.A., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett.\u00a032, 299\u2013301 (2004)","journal-title":"Oper. Res. Lett."},{"key":"32_CR31","first-page":"633","volume":"20","author":"K. Wagner","year":"1984","unstructured":"Wagner, K.: Monotonic coverings of finite sets. Elektron. Inform. Kybernet.\u00a020, 633\u2013639 (1984)","journal-title":"Elektron. Inform. Kybernet."},{"key":"32_CR32","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/s00224-005-1273-8","volume":"40","author":"G. Xu","year":"2007","unstructured":"Xu, G., Xu, J.: Constant approximation algorithms for rectangle stabbing and related problems. Theory of Computing Systems\u00a040, 187\u2013204 (2007)","journal-title":"Theory of Computing Systems"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13731-0_32.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T21:42:24Z","timestamp":1606167744000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13731-0_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642137303","9783642137310"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13731-0_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}