Solving the Minimum Crossing Number Problem Using an Improved Artificial Neural Network | SpringerLink
Skip to main content
Springer Nature Link
Log in

Solving the Minimum Crossing Number Problem Using an Improved Artificial Neural Network

  • Conference paper
Advances in Machine Learning and Cybernetics

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 3930))

Abstract

The minimum crossing number problem has important applications in printed circuit board layout, VLSI circuit routing, and automated graph drawing. In this paper, we propose an improved Hopfield neural network algorithm for efficiently solving the minimum crossing number problem. To evaluate the proposed algorithm, a large number of instances have been simulated. The simulation results show that the proposed algorithm is much better than previous works for solving the minimum crossing number problem in terms of the computation time and the solution quality.

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

Access this chapter

Log in via an institution

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. Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM J. Alg. Disc. Meth. 4, 312–316 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  2. Leighton, F.T.: New lower bound techniques for VLSI. Math. Sys. Theory 17, 47–70 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  3. Shahrokhi, F., Szekely, L.A., Sykora, O., Vrto, I.: The book crossing number of a graph. J. Graph Theory 21, 413–424 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  4. Hopfield, J.J., Tank, D.W.: Computing with neural circuits: A model. Science 233, 625–633 (1986)

    Article  Google Scholar 

  5. Cimikowski, R., Shope, P.: A neural network algorithm for a graph layout problem. IEEE Trans. on Neural Network 7, 341–345 (1996)

    Article  Google Scholar 

  6. Takefuji, Y., Lee, K.C.: Artificial neural networks for four-coloring map problems and K-colorability problems. IEEE Trans. Circuits Syst. 38, 326–333 (1991)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculty of Engineering, Fukui University, Fukui-shi, 910-8507, Japan

    Rong Long Wang & Kozo Okazaki

Authors
  1. Rong Long Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kozo Okazaki
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computing, Hong Kong Polytechnic University, P.O. Box, Hong Kong, China

    Daniel S. Yeung

  2. School of Creative Media, City University of Hong Kong,, China

    Zhi-Qiang Liu

  3. Department of Mathematics and Computer Science, Hebei University, 071002, Baoding, Hebei, P.R. China

    Xi-Zhao Wang

  4. School of Electrical and Information Engineering, University of Sydney, 2006, NSW, Australia

    Hong Yan

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Wang, R.L., Okazaki, K. (2006). Solving the Minimum Crossing Number Problem Using an Improved Artificial Neural Network. In: Yeung, D.S., Liu, ZQ., Wang, XZ., Yan, H. (eds) Advances in Machine Learning and Cybernetics. Lecture Notes in Computer Science(), vol 3930. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11739685_83

Download citation

  • DOI: https://doi.org/10.1007/11739685_83

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-33584-9

  • Online ISBN: 978-3-540-33585-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation