[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Feedback Vertex Sets in Rotator Graphs

  • Conference paper
Computational Science and Its Applications - ICCSA 2006 (ICCSA 2006)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3984))

Included in the following conference series:

Abstract

This paper provides an algorithm for finding feedback vertex set in rotator graphs. Feedback vertex set is a subset of a graph whose removal causes an acyclic graph and is developed in various topologies of interconnected networks. In 1992, Corbett pioneered rotator graphs, whose interesting topological structures attract many researchers to publish relative papers in recent years. In this paper, we first develops feedback vertex set algorithm for rotator graphs. Our algorithm utilizes the technique of dynamic programming and generates a feedback vertex set of size n!/3 for a rotator graph of scale n, which contains n! nodes. The generated set size is proved to be minimum. Finding a minimum feedback vertex set is a NP-hard problem for general graphs. The time complexity of our algorithm, which finds a minimum feedback vertex set for a rotator graph of scale n, is proved to be O(n n− − 3).

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. Corbett, P.F.: Rotator Graphs: An Efficient Topology for Point-to-Point Multiprocessor Networks. IEEE Transactions on Parallel and Distributed System 3(5), 622–626 (1995)

    Article  MathSciNet  Google Scholar 

  2. Chen, C., Agrawal, D.P., Burke, J.: dBCube: A New Class of Hierarchical Multiprocessor Interconnection Networks with Area Efficient Layout. IEEE Trans. on Parallel and Distributed Systems 4, 1332–1344 (1993)

    Article  Google Scholar 

  3. Caragiannis, C., Kaklamanis, P.: Kanellopoulos: New Bounds on The Size of The Feedback Vertex Set on Meshes and Butterflies. Information Processing Letters 83(5), 275–280 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  4. Flood, M.M.: Exact and Heuristic Algorithms for The Weighted Feedback Arc Set Problem: A special case of the skew-symmetric quadratic assignment problem. Networks 20, 1–23 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  5. Floyd, R.: Assigning Meaning to Programs. In: Proceedings of Symposium on Applied Mathematics, pp. 19–32 (1967)

    Google Scholar 

  6. Focardi, R., Luccio, F.L., Peleg, D.: Feedback Vertex Set in Hypercubes. Information Processing Letters 76(1-2), 1–5 (2000)

    Article  MathSciNet  Google Scholar 

  7. Garey, M.R., Johnson, D.S.: Computers and Intractability, Freeman, San Francisco, CA (1979)

    Google Scholar 

  8. Yannakakis, M.: Node-Deletion Problem on Bipartite Graphs. SIAM Journal on Computing 10, 310–327 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  9. Luccio, F.L.: Exact Minimum Feedback Vertex Set in Meshes and Butterflies. Information Processing Letters 66(2), 59–64 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  10. Caragiannis, I., Kaklamanis, C., Kanellopoulos, P.: New Bounds on The Size of The Feedback Vertex Set on Meshes and Butterflies. Information Processing Letters 83(5), 275–280 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  11. Focardi, R., Luccio, F.L., Peleg, D.: Feedback Vertex Set in Hypercubes. Information Processing Letters 76(1-2), 1–5 (2000)

    Article  MathSciNet  Google Scholar 

  12. Wang, F.H., Wang, Y.L., Chang, J.M.: Feedback Vertex Sets in Star Graphs. Information Processing Letters 89(4), 203–208 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  13. Kralovic, R., Ruzicka, P.: Minimum Feedback Vertex Sets in Shuffle-based Interconnection Networks. Information Processing Letters 86(4), 191–196 (2003)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Information Management, National Taiwan University of Science and Technology, Taipei, Taiwan, ROC

    Chiun-Chieh Hsu & Kung-Kuei Lin

  2. Department of Information Management, National Taipei College of Business, Taipei, Taiwan, ROC

    Hon-Ren Lin

  3. Department of Information Management, Hwa-Shia Institute of Technology, Taipei, Taiwan, ROC

    Hsi-Cheng Chang

Authors
  1. Chiun-Chieh Hsu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hon-Ren Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hsi-Cheng Chang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Kung-Kuei Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, University of Calgary,, 2500 University Drive N.W., T2N 1N4, Calgary, AB, Canada

    Marina L. Gavrilova

  2. Department of Mathematics and Computer Science, University of Perugia, via Vanvitelli, 1, I-06123, Perugia, Italy

    Osvaldo Gervasi

  3. William Norris Professor, Head of the Computer Science and Engineering Department, University of Minnesota, USA

    Vipin Kumar

  4. OptimaNumerics Ltd.,, Cathedral House 23-31 Waring Street, BT1 2DX, Belfast, UK

    C. J. Kenneth Tan

  5. Clayton School of IT, Monash University, 3800, Clayton, Australia

    David Taniar

  6. Department of Chemistry, University of Perugia, Via Elce di Sotto, 8, I-06123, Perugia, Italy

    Antonio Laganá

  7. School of Computing, Soongsil University, Seoul, Korea

    Youngsong Mun

  8. School of Information and Communication Engineering, Sungkyunkwan University, Korea

    Hyunseung Choo

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Hsu, CC., Lin, HR., Chang, HC., Lin, KK. (2006). Feedback Vertex Sets in Rotator Graphs. In: Gavrilova, M.L., et al. Computational Science and Its Applications - ICCSA 2006. ICCSA 2006. Lecture Notes in Computer Science, vol 3984. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11751649_17

Download citation

  • DOI: https://doi.org/10.1007/11751649_17

  • Publisher Name: Springer, Berlin, Heidelberg

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

  • Online ISBN: 978-3-540-34080-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation