Abstract
Finding optimal solutions in the graph bisection problem is a notoriously hard task. One of the main reasons is the barriers which prevent search algorithms from reaching the optimal solutions. Given an algorithm for finding optimal solutions, the search process can be represented by a Markov chain. Every two neighboring solutions has a connection in the chain with a transition probability. If the algorithm is deterministic, many of the connections are set to the probability zero since they can never be chosen in the algorithm. It thus may happen that there is no path with a positive probability. We suggest a method to open paths with zero or near-zero transition probability by implicitly changing the chain, which we believe will eventually make the search more flexible. Experimental results showed significant improvement over traditional representative partitioning methodologies, the Fiduccia-Mattheyses algorithm and its two-phase variant.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alpert, C., Kahng, A.B.: A general framework for vertex orderings, with applications to netlist clustering. In: Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pp. 63–67 (1994)
Alpert, C.J., Kahng, A.B.: Recent directions in netlist partitioning: A survey. Integration, the VLSI Journal 19(1-2), 1–81 (1995)
Battiti, R., Bertossi, A.: Greedy, prohibition, and reactive heuristics for graph partitioning. IEEE Transactions on Computers 48(4), 361–385 (1999)
Bui, T.N., Heigham, C., Jones, C., Leighton, T.: Improving the performance of the Kernighan-Lin and simulated annealing graph bisection algorithms. In: Proceedings of the 26th ACM/IEEE Design Automation Conference, pp. 775–778 (1989)
Bui, T.N., Moon, B.-R.: Genetic algorithm and graph partitioning. IEEE Transactions on Computers 45(7), 841–855 (1996)
Choe, T.-Y., Park, C.-I.: A k-way graph partitioning algorithm based on clustering by eigenvector. In: Proceedings of the Fourth International Conference on Computational Science, pp. 598–601 (2004)
Cong, J., Lim, S.K.: Edge separability-based circuit clustering with application to multilevel circuit partitioning. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 23(3), 346–357 (2004)
Dhillon, I., Guan, Y., Kulis, B.: A fast kernel-based multilevel algorithm for graph clustering. In: Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge discovery in data mining, pp. 629–634 (2005)
Fiduccia, C., Mattheyses, R.: A linear time heuristics for improving network partitions. In: Proceedings of the 19th ACM/IEEE Design Automation Conference, pp. 175–181 (1982)
Garey, M., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)
Goldberg, D.: Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading (1989)
Huang, M.L., Nguyen, Q.V.: A fast algorithm for balanced graph clustering. In: Proceedings of the Eleventh International Conference on Information Visualization, pp. 46–52 (2007)
Hwang, I., Kim, Y.-H., Moon, B.-R.: Multi-attractor gene reordering for graph bisection. In: Proceedings of the Eighth Annual Conference on Genetic and Evolutionary Computation, pp. 1209–1216 (2006)
Johnson, D.S., Aragon, C., McGeoch, L., Schevon, C.: Optimization by simulated annealing: An experimental evaluation, Part 1, graph partitioning. Operations Research 37, 865–892 (1989)
Kernighan, B., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell Systems Technical Journal 49, 291–307 (1970)
Kim, Y.-H., Moon, B.-R.: Investigation of the fitness landscapes in graph bipartitioning: An empirical study. Journal of Heuristics 10(2), 111–133 (2004)
Kim, Y.-H., Moon, B.-R.: Lock-gain based graph partitioning. Journal of Heuristics 10(1), 37–57 (2004)
Kirkpatrick, S., Gelatt Jr., C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983)
Martin, O.C., Otto, S.W., Felten, E.W.: Large-step Markov chains for the traveling salesman problem. Complex Systems 5(3), 299–326 (1991)
Merz, P., Freisleben, B.: Fitness landscapes, memetic algorithms, and greedy operators for graph bipartitioning. Evolutionary Computation 8(1), 61–91 (2000)
Moraglio, A., Kim, Y.-H., Yoon, Y., Moon, B.-R.: Geometric crossovers for multiway graph partitioning. Evolutionary Computation 15(4), 445–474 (2007)
Saha, B., Mitra, P.: Dynamic algorithm for graph clustering using minimum cut tree. In: Proceedings of the Sixth IEEE International Conference on Data Mining Workshops, pp. 667–671 (2006)
Schaeffer, S.E.: Graph clustering. Computer Science Review 1(1), 27–64 (2007)
Wang, J., Peng, H., Hu, J., Yang, C.: A graph clustering algorithm based on minimum and normalized cut. In: Proceedings of the Seventh International Conference on Computational Science, pp. 497–504 (2007)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kim, YH. (2008). An Enzyme-Inspired Approach to Surmount Barriers in Graph Bisection. In: Gervasi, O., Murgante, B., Laganà, A., Taniar, D., Mun, Y., Gavrilova, M.L. (eds) Computational Science and Its Applications – ICCSA 2008. ICCSA 2008. Lecture Notes in Computer Science, vol 5072. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-69839-5_63
Download citation
DOI: https://doi.org/10.1007/978-3-540-69839-5_63
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69838-8
Online ISBN: 978-3-540-69839-5
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science
