Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Minimum Vertex Cover in Rectangle Graphs

  • Conference paper
Algorithms – ESA 2010 (ESA 2010)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 6346))

Included in the following conference series:

Abstract

We consider the Minimum Vertex Cover problem in intersection graphs of axis-parallel rectangles on the plane. We present two algorithms: The first is an EPTAS for non-crossing rectangle families, rectangle families \(\mathcal{R}\) where R 1 ∖ R 2 is connected for every pair of rectangles \(R_1,R_2 \in \mathcal{R}\). This algorithm extends to intersection graphs of pseudo-disks. The second algorithm achieves a factor of (1.5 + ε) in general rectangle families, for any fixed ε> 0, and works also for the weighted variant of the problem. Both algorithms exploit the plane properties of axis-parallel rectangles.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Kőnig, D.: Gráfok és mátrixok. Matematikai és Fizikai Lapok 38, 116–119 (1931)

    Google Scholar 

  2. Karp, R.: Reducibility among combinatorial problems. In: Complexity of Computer Computation, pp. 85–103 (1972)

    Google Scholar 

  3. Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)

    MATH  Google Scholar 

  4. Hochbaum, D.: Approximation Algorithms for NP-hard Problems. PWS Publishing Company (1997)

    Google Scholar 

  5. Vazirani, V.: Approximation Algorithms. Springer (2003)

    Google Scholar 

  6. Downey, R., Fellows, M.: Parameterized Complexity. Springer, Heidelberg (1999)

    Google Scholar 

  7. Bar-Yehuda, R., Even, S.: A linear time approximation algorithm for the weighted vertex cover problem. J. Algorithm 2, 198–203 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  8. Clarkson, K.: A modification of the greedy algorithm for vertex cover. Inform. Process. Lett. 16, 23–25 (1983)

    Article  MathSciNet  Google Scholar 

  9. Hochbaum, D.: Approximation algorithms for the set covering and vertex cover problems. SIAM J. Comput. 11(3), 555–556 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  10. Nemhauser, G.L., Trotter, L.E.: Vertex packings: structural properties and algorithms. Mathematical Programming 8, 232–248 (1975)

    Article  MATH  MathSciNet  Google Scholar 

  11. Bar-Yehuda, R., Even, S.: A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics 25, 27–46 (1985)

    MathSciNet  Google Scholar 

  12. Monien, B., Speckenmeyer, E.: Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Informatica 22(1), 115–123 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  13. Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J. Comput. 31(5), 1608–1623 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  14. Karakostas, G.: A better approximation ratio for the vertex cover problem. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 1043–1050. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  15. Dinur, I., Safra, S.: The importance of being biased. In: 34th annual ACM Symposium on Theory of Computing, pp. 33–42 (2002)

    Google Scholar 

  16. Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comput. 1(2), 180–187 (1972)

    Article  MATH  MathSciNet  Google Scholar 

  17. Lipton, R., Tarjan, R.: Applications of a planar separator theorem. SIAM J. Comput. 9(3), 615–627 (1980)

    Article  MATH  MathSciNet  Google Scholar 

  18. Bar-Yehuda, R., Even, S.: On approximating a vertex cover for planar graphs. In: 14th Annual ACM STOC, pp. 303–309 (1982)

    Google Scholar 

  19. Chiba, N., Nishizeki, T., Saito, N.: Applications of the Lipton and Tarjan’s planar separator theorem. Journal of information processing 4(4), 203–207 (1981)

    MATH  MathSciNet  Google Scholar 

  20. Baker, B.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153–180 (1994)

    Article  MATH  Google Scholar 

  21. Chalermsook, P., Chuzhoy, J.: Maximum independent set of rectangles. In: 20th Annual ACM-SIAM SODA, pp. 892–901 (2009)

    Google Scholar 

  22. Khanna, S., Muthukrishnan, S., Paterson, M.: On approximating rectangle tiling and packing. In: 9th annual ACM-SIAM SODA, 384–393 (1998)

    Google Scholar 

  23. Agarwal, P.K., van Kreveld, M.J., Suri, S.: Label placement by maximum independent set in rectangles. Comput. Geom. 11(3-4), 209–218 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  24. Doerschler, J., Freeman, H.: A rule-based system for dense-map name placement. Communications of the ACM 35(1), 68–79 (1992)

    Article  Google Scholar 

  25. Freeman, H.: Computer name placement. In: Geographical Information Systems: Principles and Applications, pp. 445–456 (1991)

    Google Scholar 

  26. Lewin-Eytan, L., Naor, J., Orda, A.: Admission control in networks with advance reservations. Algorithmica 40(4), 293–304 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  27. Fowler, R., Paterson, M., Tanimoto, S.: Optimal packing and covering in the plane are NP-complete. Inform. Process. Lett. 12(3), 133–137 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  28. Asano, T.: Difficulty of the maximum independent set problem on intersection graphs of geometric objects. In: 6th ICTAG (1991)

    Google Scholar 

  29. Berman, P., DasGupta, B., Muthukrishnan, S., Ramaswami, S.: Efficient approximation algorithms for tiling and packing problems with rectangles. J. Algorithm 41 (2001)

    Google Scholar 

  30. Chan, T.: A note on maximum independent sets in rectangle intersection graphs. Inform. Process. Lett. 89(1), 19–23 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  31. Chan, T.M., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. In: 25th annual ACM SOCG, pp. 333–340 (2009)

    Google Scholar 

  32. Chan, T.M.: Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithm 46 (2003)

    Google Scholar 

  33. Erlebach, T., Jansen, K., Seidel, E.: Polynomial-time approximation schemes for geometric intersection graphs. SIAM J. Comput. 34 (2005)

    Google Scholar 

  34. Marx, D.: Efficient approximation schemes for geometric problems? In: 13th annual European Symposium on Algorithms, pp. 448–459 (2005)

    Google Scholar 

  35. van Leeuwen, E.J.: Better approximation schemes for disk graphs. In: 10th Scandinavian Workshop on Algorithm Theory, pp. 316–327 (2006)

    Google Scholar 

  36. Apostolico, A., Atallah, M., Hambrusch, S.: New clique and independent set algorithms for circle graphs. Discrete Appl. Math. 36(1), 1–24 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  37. Cenek, E., Stewart, L.: Maximum independent set and maximum clique algorithms for overlap graphs. Discrete Appl. Math. 131(1), 77–91 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  38. Golumbic, M., Hammer, P.: Stability in circular arc graphs. J. Algorithm 9(3), 314–320 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  39. Hsu, W.L., Tsai, K.H.: Linear time algorithms on circular-arc graphs. Inform. Process. Lett. 40(3), 123–129 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  40. Golumbic, M.: Algorithmic graph theory and perfect graphs. Academic Press, New York (1980)

    MATH  Google Scholar 

  41. Golumbic, M., Trenk, A.: Tolerance Graphs. Cambridge University Press, Cambridge (1985)

    Google Scholar 

  42. Chlebík, M., Chlebíková, J.: Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes. In: 16th Annual ACM-SIAM SODA 2005, pp. 267–276 (2005)

    Google Scholar 

  43. Hochbaum, D., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32(1), 130–136 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  44. Bar-Yehuda, R., Halldórsson, M.M., Naor, J., Shachnai, H., Shapira, I.: Scheduling split intervals. SIAM J. Comput. 36(1), 1–15 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  45. Butman, A., Hermelin, D., Lewenstein, M., Rawitz, D.: Optimization problems in multiple-interval graphs. In: 18th annual ACM-SIAM SODA, pp. 268–277 (2007)

    Google Scholar 

  46. Agarwal, P.K., Sharir, M.: Arrangements and their applications. In: Handbook of Computational Geometry, pp. 49–119 (1998)

    Google Scholar 

  47. Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithm 7, 309–322 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  48. Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)

    Book  MATH  Google Scholar 

  49. Sharir, M., Agarwal, P.K.: Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, Cambridge (1995)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Technion IIT, Haifa, 32000, Israel

    Reuven Bar-Yehuda

  2. Max-Planck-Institut für Informatik, Saarbrücken, Germany

    Danny Hermelin

  3. School of Electrical Engineering, Tel-Aviv University, Tel-Aviv, 69978, Israel

    Dror Rawitz

Authors
  1. Reuven Bar-Yehuda
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Danny Hermelin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Dror Rawitz
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Mathematics and Computing Science, TU Eindhoven, Eindhoven, The Netherlands

    Mark de Berg

  2. Institute for Computer Science, J.W. Goethe University, 60325, Frankfurt/Main, Germany

    Ulrich Meyer

Rights and permissions

Reprints and permissions

Copyright information

© 2010 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bar-Yehuda, R., Hermelin, D., Rawitz, D. (2010). Minimum Vertex Cover in Rectangle Graphs. In: de Berg, M., Meyer, U. (eds) Algorithms – ESA 2010. ESA 2010. Lecture Notes in Computer Science, vol 6346. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15775-2_22

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-15775-2_22

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-15774-5

  • Online ISBN: 978-3-642-15775-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation