Neural networks and graph theory

Peretto, P., An Introduction to the Modeling of Neural Networks, London: Cambridge University Press, 1992. Gallant, S. I., Neural Network Learning and Expert Systems, Cambridge: The MIT Press, 1993. Bondy, J. A., Murty, U. S. R., Graph Theory with Application, London, Basingtoke, New York: The MacMillan Press LTD, 1976. Hopfield, J. J., Tank, D. W., Neural computation of dicisions optimization problem, Biol. Cybernetics, 1985, 52: 141–152. Gibbons, A., Algorithmic Graph Theory, Cambridge, London, New York: Cambridge University Press, 1985. Dahl, E. D., Neural network algorithm for an NP-complete problem: map and graph coloring, Proc. IEEE First International Conference on Neural Networks, Vol. III, June, San Diego, New York: IEEE, 1987, 113–120. Xu, Jin, Zhang Junvin, Bao Zheng, Coloring alogorithm of graph theory based on Hopfield neural network, Acta Electronica Sinica, 1996, 24(10): 8–13. Ma Songde, Artificial neural networks and optimization, Proceedings of the First Chinese Conference on Articifial Neural Networks, Beijing (in Chinese), Beijing: China Neural Network Society, 1990, 22–28. Chen Guoliang, Optimal problems based on ANN, Proceedings of the First Chinese Conference on Articifial Neural Networks, Beijing (in Chinese), Beijing: China Neural Network Society, 1990, 122–129. Liang Weufa et al., Some algorithms of hard graph theory problems based on artificial neural networks, Proceedings of the First Chinese Conference on Articifial Neural Networks, Beijing (in Chinese), Beijing: China Neural Network Society, 1990, 924–927. Xu Jin, Zhang, J. Y., Bao, Z., A new isomorphic algorithm based on Hopfield neural networks, Journal of Electronics, 1996, 18: 116–121. Xu Jin, Self-complementary Graph Theory with Applications: Chapter 6, Xi'an: Xidian University Press, 1999. Bron, C., Kerbosch, J., Finging all cliques of an undirected graph, Commun. Ass. Mach., 1973, 16: 575–577. Gendreau, M., Picard, J. C., Zubieta, L., An efficient implicit enumeration algorithm for the maximum clique problem, Lecture Notes in Economics and Mathematical Systems (eds. Kurzhanski, A. et al.), New York: Springer-Verlag, 1988, 304: 79–91. Mitten, L. G., Branch and bound method: general formulation and properties, Ops. Res., 1970, 18: 24–34. Robson, J. M., Algorithms for maximum independent sets, J. Algorithm, 1986, 7: 425–440. Tarjan, R. E., Trojanowski, A. E., Finding a maximum independent set, SIAM JL Comput., 1977, 6: 537–546. Balas, E., Yu, C. S., Finging the maximum clique in an arbitrary graph, SIAM JL Comput., 1986, 15: 1054–1068. Panos, M. P., Gregory, P. R., A brance and bound algorithm for the maximum clique problem, Computers Ops. Res., 1992, 19(5): 363–375. Zhang, J. Y., Xu Jin, Bao, Z., A new algorithm of the maximum clique and the maximum independent set problems based on Hopfield neural network, Journal of Electronics, 1996, 18(sup): 121–127. Booth, K. S., Lueker, G. S., Testing the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. Syst. Sci., 1976, 13: 335–379. Hopcroft, J. E., Tarjan, R. E., Efficient planarity testing of graphs,J. Assoc. Comput. Mach., 1974, 21: 549–568. Lempel, A., Evens, S., Cederbaum, I., An algorithm for planarity testing of graphs, Theory of Graph (ed. Rosenstiehl, P.), New York: Gordon and Breach, 1967, 215–232. Shih, W. K., Hsu, W. L., A simple test for planar graphs, Proceedings of the Third China-USA International Conference on Graph Theory, Beijing (eds. Alavi, Y., Lick, D. R., Liu Jinqiang), Singapore: World Scientific, 1994, 21–28. Takefuji, Y., A near-optimum parallel planarizatio algorithm, Science, 1989, 245: 1221–1223. Xu Jin, Gao Lin, Zhang, J. Y., A new algorithm of planar graphs based on neural networks, Journal of Xidian University, 2001, (2): 1–5. Wilson, G. V., Pawley, G. S., On stability of the traveling salesman problem algorithm of Hopfield and tank, Bio. Cybern., 1988, 58: 63–70. Aiyer, S. V. B., Niranjan, M., Fallside, F., A theoretical investigation into the performance of the Hopfield model, IEEE Trans on Neural Network, 1990, 1(2): 204–215. Sun, S. Y., Zheng, J. L., A modified algorithm and theoretical analysis for Hopfield network solving TSP, Acta Electronica Sinica, 1995, 23(1): 73–78. Zhang, Y. J., Ye, Z. X., Neural Networks with Applications—94' New Advance (in Chinese), Wuhan: The Huazhong University of Science and Technologicl Press, 1994. Yu Daoheng, An improved neural network algorithm for TSP problem, Proceedings of the First Chinese Conference on Articifial Neural Networks (in Chinese), Beijing: China Neural Network Society, 1990, 116–121. Jin Fan, Hu Fei, Chang Jianwu, A solution of C-TSP based on Hopfield Network, Proceedings of the First Chinese Conference on Articifial Neural Networks, Beijing (in Chinese), Beijing: China Neural Network Society, 1990, 122–129. Fan Shemin, Ph. D. Thesis, Xi'an: Xi'an Jiaotong University, 1993. Sanchis, L., Multiple-way network partitioning, IEEE Trans. Computers, 1989, 38: 62–81. Fox, G. C., A review of automatic load balancing and decomposition methods for the Hypercube, Numerical Alorithms for Modern Parallel Computer Architectures (ed. Schultz, M.), New York: Springer-Verlag, 1988, 63–76. Simon, H. D., Partitioning of unstructured problems for parallel processing, Computing Systems in Eng., 1991, 2: 135–148. Williams, R., Unification for spectral and intertial bisection, Technical Report, California Inst. of Technology, 1994, Available at: http://www.carcr.caltech.edu/roy/paper/ Hendrickson, B., Leland, R., An improved spectral graph partitioning algorithm for mapping parallel computations, SIAM J. Scientific Computing, 1995, 16(2): 45–469. Gilbert, J. R., Miller, G. L., Teng, S. H., Geometric mesh partitioning: Implementation and experiments, Proc. International First Parallel Processing Symp., (IPPS'95), 1995. Boppana, R. B., Eigenvalues and graph bisection: An average case analysis, Proc. 28th Symp. Foundations of Computer Science, 1987, 280–285. Bui, T. N., Chaudhuri, S., Leighton, F. T. et al., Graph bisection algorithms with good average case behavior, Combinatorica, 1987, 7(2): 171–191. Bui, T. N., Peck, A., Partitioning planar graphs, SIAM J. Computing, 1992, 21(2): 203–215. Garey, M., Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, San Francisco: Freeman, 1979. Bui, T. N., Jones, C., Finding good approximate vertex and edge partitions is NP-hard, Information Processing Letters, 1992, 42: 153–159. Leighton, F. T., Rao, S., An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms, Proc. 29th Symp. Foundations of Computer Science, 1988, 422–431. Farhat, C., A simple and efficient automatic FEM domain decomposer, Computers and Structures, 1988, 28(5): 579–602. Farhat, C., Lanteri, S., Simon, H. D., TOP/DOMDEC—A software tool for mesh partitioning and parallel processing, J. Computing Systems in Eng., 1995, 6(1): 13–26. Laguna, M., Feo, T. A., Elrod, H. C., A greedy randomized adaptive search procedure for the two-partition problems, Operations Research, 1994, 42: 677–687. Battiti, R., Bertossi, A. A., Differential greedy for the 0–1 equicut problem, Network Design: Connectivity and Facilities Location (eds. Du, D. Z., Pardalos, P. M.), Princeton: Amer. Math. Soc., 1997, 3–22. Johnson, D. S., Aragon, C. R., Mcgeoch, L. A. et al., Optimization by simulated annealing: An experimental evaluation; Part I, Graph Partitioning, Operations Research, 1989, 37: 865–892. Kirkpatrick, S., Optimization by simulated annealing: Quantitative studies, J. Statistical Physics, 1994, 34: 975–986. Kirkpatrick, S., Gelatt, C. D. Jr., Vecchi, M. P., Optimization by simulated annealing, Science, 1983 (May), 220 (4598): 671–680. Rutebar, R., Simulated annealing algorithms: An overview, IEEE Circuit and Devices Magazine, 1989, 19–26. Sechen, C., Sangiovanni-Vincetelli, A., Timberwolf3.2: A new standard cell placement and global routing package, Proc. 23rd ACM/IEEE Design Automation Conf., 1986, 432–339. Sun, W., Sechen, C., Efficient and Effective placement for very large circuits, IEEE Trans. Computer-Aided Design, 1995, 14(3): 349–359. Battiti, R., Bertossi, A. A., Greedy, prohibition, and reactive heuristics for graph partitioning, IEEE Trans. on Computers, 1999, 48(4): 361–385. Bui, T. N., Moon, B. R., Genetic algorithm and grpah partitioning, IEEE Trans. Computers, 1996, 45(7): 841–855. Kernighan, B., Lin, S., An efficient heuristic procedure for partitioning graphs, Bell Systems Technical J., 1970, 49(2): 291–307. Fiduccia, C., Mattheyses, M., A linear time heuristics for improving network partitions, Proc. 19th ACM/IEEE Deisgn Automation Conf., Las Vegas, 1993, 175–181. Hendrickson, H., Leland, R., A multilevel algorithm for partitioning graphs, Technical Report SAND93-1301, SANDIA Nat'l Laboratory 1993. Diekmann, R., Monien, B., Preis, R., Using helpful sets to improve graph bisections, Interconnection Networks and Mapping and Scheduling Parallel Computations (eds. Hsu, D. F., Rosenberg, A. L., Sotteau, D.), Amer. Math. Soc., 1995, 57–73. Glover, F., Tabu Search-Part I, ORSA, J. Computing, 1989, 1(3): 190–260. Rolland, E., Pirkul, H., Glover, F., A tabu search for graph partitioning, Annals of Operations Research, Metaheurisitcs in Combinatorial Optimization, 1996, 63: 46–53. Dell'Amico, M., Maffioli, F., A new Tabu search approach to the 0–1 equicut problem, Meta-Heuristics 1995: The State of the Art, Dordrecht: Kluwer Academic, 1996, 361–377. Pirkul, H., Rolland, E., New heuristic solution procedures for the uniform graph partitioning problem: Extensions and evaluation, Computers and Operations Research, 1994, 21(8): 895–907. Rolland, E., Pirkul, H., Heuristic solution procedures for the graph partitioning problem, Computer Science and Operations Research: New Developments in Their Interfaces (ed. Balci, O.), Oxford: Pergamon Press, 1992. Bui, T. N., Jones, C., A heuristic for reducing fill in sparse matrix factorization, Proc. Sixth SIAM Conf. Parallel Processing for Scientific Computing, Philadelphia: SIAM, 1993, 445–452. Garey, M. R., Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-completeness, San Francisco, New York: Freeman, 1979. Orlova, G. I., Dorfman, Y. G., Finding the maximum cut in a graph, Eng. Cybern., 1972, 10: 502–506. Poljak, S., Turzik, D., Max-cut in circulant graphs, Discrete Mathemaics, 1992, 108: 379–392. Hsu, C. P., Minimum-via topological routing, IEEE Trans. CAD/ICAS, 1983, (CAD) 2(4): 235–246. Barahona, F., Grötschel, M., Jünger, M. et al., An application of combinatorial optimuzation to statistical physics and circuit layout design, Oper. Res., 1988, 36(3): 493–513. Delorme, C., Poljak, S., Laplacian eigenvalues and the maximum cut problem, Math. Program., 1993, 62: 557–574. Delorme, C., Poljak, S., The performance of an eigenvalue bound on the max-cut problem in some classes of graphs, Discrete Math., 1993, 111: 145–156. Poljak, S., Rendl, F., Note and edge relaxations of the max-cut problem, Computing, 1994, 52: 123–137. Korst, J. H. M., Aarts, E. H. L., Combinatorial optimization on a Boltzmann machine, J. Paral. Dist. Comput., 1989, 6: 331–357. Funabiki, N., Nishiawa, S., Tajima, S., A binary neural network approach for max cut problems, ICONIP'96-Hong Kong, Hong Kong: The Chinese Univ. Press, 1996, 631–635. Battiti, R., Albert, B. A., Greedy, prohibition, and reactive heuristes fir graph partitioning, IEEE Trans. on Computers, 1999, 48(4): 361–385. Ramanujam, J., Sadayapan, P., Optimization by neural networks, Proc. IEEE Int'l Conf. on Neural Networks, II, 1988, 325–332. Foo, Y. S., Takefuji, Y., Stochastic neural networks for solving job-shop scheduling: Part I: problem presentation, Proc. IEEE Int'l Conf. on Neural Networks, II, San Diego, New York: IEEE, 1988, 283–290. Chen Guoliang, Neurocomputing with applications in optimization, Journal of Computer Science and Development, 1992, (5): 1–21. Hopfield, J. J., Tank, D. W., Simple neural optimization nerworks: an A/D converter, signal decision circuit, and a linear programming circuit, IEEE Trans. on CAS, 1986, 33(5): 533–541. Liou, C. Y., Chang, Q. M., Numerical soap film for the Steiner tree problem, ICONIP'96-Hong Kong, Hong Kong: The Chinese Univ. Press, 1996, 642–648. Bruck, J., On the convergence properties of the Hopfield model, Proceedings of the IEEE, 1990, 78(10): 1579–1585. Goles, E., Antisymmetrical neural networks, Discrete Applied Mathematics, 1986, 13: 97–100. Xu, J., Bao, Z., The stability of Antisymmetrical discrete Hopfield neural networks, Acta Electronica Sinica, 1999, 27(1): 103–107. Xu Jin, Bao, Z., The linear separability of a Boolean function (I)—the fundational ofn-dimensional hypercubes, Journal of Electronics, 1996, 18: 6–13. Xu Jin, Bao, Z., Linear separability of Boolean function (II), Journal of Electronics, 1996, 18: 14–21 Goles, E., Fogelman, F., Pellegrin, D., Decreasing energy functions as a tool for studying threshold networks, Discrete Applied Mathematics, 1985, 12: 261–277.