Minimum Bisection Is NP-hard on Unit Disk Graphs

1. Akyildiz, I., Su, W., Sankarasubramaniam, Y., Cayirci, E.: Wireless sensor networks: A survey. Computer Networks 38, 393–422 (2002)

   Google Scholar 

2. Bichot, C.-E., Siarry, P. (eds.): Graph Partitioning. Wiley (2011)

   Google Scholar 

3. Bradonjic, M., Elsässer, R., Friedrich, T., Sauerwald, T., Stauffer, A.: Efficient broadcast on random geometric graphs. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1412–1421 (2010)

   Google Scholar 

4. Breu, H., Kirkpatrick, D.G.: Unit disk graph recognition is NP-hard. Computational Geometry 9(1-2), 3–24 (1998)

   MATH  MathSciNet  Google Scholar 

5. Bui, T., Chaudhuri, S., Leighton, T., Sipser, M.: Graph bisection algorithms with good average case behavior. Combinatorica 7, 171–191 (1987)

   MathSciNet  Google Scholar 

6. Cygan, M., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Minimum bisection is fixed parameter tractable. In: Proceedings of the 46th Annual Symposium on the Theory of Computing, STOC (to appear, 2014)

   Google Scholar 

7. Delling, D., Goldberg, A.V., Razenshteyn, I., Werneck, R.F.: Exact combinatorial branch-and-bound for graph bisection. In: Proceedings of the 14th Meeting on Algorithm Engineering & Experiments (ALENEX), pp. 30–44 (2012)

   Google Scholar 

8. Díaz, J., Penrose, M.D., Petit, J., Serna, M.J.: Approximating layout problems on random geometric graphs. Journal of Algorithms 39(1), 78–116 (2001)

   MATH  MathSciNet  Google Scholar 

9. Díaz, J., Petit, J., Serna, M.: A survey on graph layout problems. ACM Computing Surveys 34, 313–356 (2002)

   Google Scholar 

10. Feldmann, A.E., Widmayer, P.: An \(\mathcal{O}(n^4)\) time algorithm to compute the bisection width of solid grid graphs. In: Demetrescu, C., Halldórsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 143–154. Springer, Heidelberg (2011)

    Google Scholar 

11. Garey, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman & Co. (1979)

    Google Scholar 

12. Hromkovic, J., Klasing, R., Pelc, A., Ruzicka, P., Unger, W.: Dissemination of Information in Communication Networks - Broadcasting, Gossiping, Leader Election, and Fault-Tolerance. In: Texts in Theoretical Computer Science. An EATCS Series, Springer, Heidelberg (2005)

    Google Scholar 

13. Jansen, K., Karpinski, M., Lingas, A., Seidel, E.: Polynomial time approximation schemes for Max-Bisection on planar and geometric graphs. SIAM Journal on Computing 35(1), 110–119 (2005)

    MATH  MathSciNet  Google Scholar 

14. Kahruman-Anderoglu, S.: Optimization in geometric graphs: Complexity and approximation. PhD thesis, Texas A & M University (2009)

    Google Scholar 

15. Karpinski, M.: Approximability of the minimum bisection problem: An algorithmic challenge. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol. 2420, pp. 59–67. Springer, Heidelberg (2002)

    Google Scholar 

16. Kernighan, B., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal 49(2), 291–307 (1970)

    MATH  Google Scholar 

17. Kratochvíl, J.: Intersection graphs of noncrossing arc-connected sets in the plane. In: Proceedings of the 4th Int. Symp. on Graph Drawing (GD), pp. 257–270 (1996)

    Google Scholar 

18. MacGregor, R.: On partitioning a graph: A theoretical and empirical study. PhD thesis, University of California, Berkeley (1978)

    Google Scholar 

19. Papadimitriou, C.H., Sideri, M.: The bisection width of grid graphs. Mathematical Systems Theory 29(2), 97–110 (1996)

    MATH  MathSciNet  Google Scholar 

20. Räcke, H.: Optimal hierarchical decompositions for congestion minimization in networks. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pp. 255–264 (2008)

    Google Scholar 

Download references