An \(O(n^4)\) Time Algorithm to Compute the Bisection Width of Solid Grid Gra
详细信息 查看全文
- 作者：Andreas Emil Feldmann ; Peter Widmayer
- 关键词：Bisection ; Solid grid graphs ; Planar graphs
- 刊名：Algorithmica
- 出版年：2015
- 出版时间：January 2015
- 年：2015
- 卷：71
- 期：1
- 页码：181-200
- 全文大小：485 KB
- 参考文献：1. Cygan, M., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Minimum bisection is fixed parameter tractable. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), pp. 323-32 (2014)
2. Díaz J., Mertzios, G.: Minimum bisection is np-hard on unit disk graphs. In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS ), To appear (2014)
3. Díaz, J., Petit, J., Serna, M.J.: A survey of graph layout problems. ACM Comput. Surv. 34(3), 313-56 (2002) CrossRef
4. Díaz, J., Serna, M.J., Torán, J.: Parallel approximation schemes for problems on planar graphs. Acta Inform. 33(4), 387-08 (1996) CrossRef
5. Diks, K., Djidjev, H.N., Sykora, O., Vrto, I.: Edge separators of planar and outerplanar graphs with applications. J. Algorithm. 14(2), 258-79 (1993) CrossRef
6. Feldmann, A.E.: Balanced Partitioning of Grids and Related Graphs: A Theoretical Study of Data Distribution in Parallel Finite Element Model Simulations. PhD thesis, ETH Zurich, April 2012. Diss.-Nr. ETH: 20371
7. Feldmann, A.E., Das, S., Widmayer, P.: Corner cuts are close to optimal: from solid grids to polygons and back. Discrete Appl. Math. 161(7-), 970-98 (2013) CrossRef
8. Feldmann, A.E., Widmayer, P.: An \(O(n^4)\) time algorithm to compute the bisection width of solid grid graphs. In Proceedings of the 19th Annual European Symposium on Algorithms (ESA), pp. 143-54 (2011)
9. Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237-67 (1976) CrossRef
10. Khot, S.: Ruling out PTAS for graph min-bisection, dense \(k\) -subgraph, and bipartite clique. SIAM J. Comput. 36(4), 1025-071 (2006) CrossRef
11. MacGregor, R.M.: On Partitioning a Graph: A Theoretical and Empirical Study. PhD thesis, University of California, Berkeley (1978)
12. Papadimitriou, C., Sideri, M.: The bisection width of grid graphs. Theory Comput. Syst. 29, 97-10 (1996)
13. Park, J.K., Phillips., C.A.: Finding minimum-quotient cuts in planar graphs. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC), pp. 766-75 (1993)
14. 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-64 (2008)
15. van Bevern, R., Feldmann, A.E., Sorge, M., Suchy, O.: On the parameterized complexity of computing graph bisections. Theory. Comput. Syst. (2014). To appear - 刊物类别：Computer Science
- 刊物主题：Algorithm Analysis and Problem Complexity
Theory of Computation
Mathematics of Computing
Algorithms
Computer Systems Organization and Communication Networks
Data Structures, Cryptology and Information Theory - 出版者：Springer New York
- ISSN：1432-0541
文摘
The bisection problem asks for a partition of the \(n\) vertices of a graph into two sets of size at most? \(\lceil n/2\rceil \) , so that the number of edges connecting the sets is minimised. A grid graph is a finite connected subgraph of the infinite two-dimensional grid. It is called solid if it has no holes. Papadimitriou and Sideri (Theory Comput Syst 29:97-10, 1996) gave an \(O(n^5)\) time algorithm to solve the bisection problem on solid grid graphs. We propose a novel approach that exploits structural properties of optimal cuts within a dynamic program. We show that our new technique leads to an \(O(n^4)\) time algorithm.