Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Combinatorial Algorithms for Listing Paths in Minimal Change Order

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNCCN,volume 4852))

Included in the following conference series:

  • 388Accesses

Abstract

Combinatorial algorithms that list combinatorial objects in minimal change order are of fundamental interest in computer science and mathematics. In minimal change ordering, successive elements differ in some pre-specified small way. In this paper, we deal with the generation of paths in a special type of minimal change ordering, the revolving door ordering. We propose a simple algorithm to list all paths in a complete graph,Kn, withn vertices in revolving door order such that each path is generated exactly once. The algorithm is built using space and time efficient schemes that list all spanning paths and “path sets” in revolving door order. Our algorithm is optimal in the sense that it operates in constant amortized time (CAT) and uses linear space.

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

Access this chapter

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Nijenhuis, A., Wilf, H.S.: Combinatorial Algorithms for Computers and Calculators. Academic Press, London (1978)

    MATH  Google Scholar 

  2. Trotter, F.H.: Perm (algorithm 115). Communications of the ACM 8, 434–435 (1962)

    Article  Google Scholar 

  3. Ruskey, F., Williams, A.: Generating combinations by prefix shifts. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 570–576. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  4. Harada, K.: Generation of rosary permutations expressed in hamiltonian circuits. Communications of the ACM 14, 373–379 (1971)

    Article MATH MathSciNet  Google Scholar 

  5. Knuth, D.E.: Art of Computer Programming, vol. 4. Addison-Wesley, Reading (2005)

    MATH  Google Scholar 

  6. Korsh, J., Lafollette, P.: A loopless gray code for rooted trees. ACM Trans. Algorithms 2(2), 135–152 (2006)

    Article MathSciNet  Google Scholar 

  7. Langdon, G.G.: An algorithm for generating permutations. Communications of the ACM 10, 298–299 (1967)

    Article  Google Scholar 

  8. Savage, C.: A survey of combinatorial Gray codes. SIAM Review 39(4), 605–629 (1997)

    Article MATH MathSciNet  Google Scholar 

  9. Johnson, S.M.: Generation of permutations by adjacent transposition. Math. Comp. 17, 282–285 (1963)

    Article MATH MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, National University of Computer and Emerging Sciences, Block B, Faisal Town, Lahore, Pakistan

    Zareen Alamgir

  2. Center for Advanced Studies in Mathematics, Lahore University of Management Sciences, Opposite Sector “U”, DHA, Lahore, Pakistan

    Sarmad Abbasi

Authors
  1. Zareen Alamgir

    You can also search for this author inPubMed Google Scholar

  2. Sarmad Abbasi

    You can also search for this author inPubMed Google Scholar

Editor information

Jeannette Janssen Paweł Prałat

Rights and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Alamgir, Z., Abbasi, S. (2007). Combinatorial Algorithms for Listing Paths in Minimal Change Order. In: Janssen, J., Prałat, P. (eds) Combinatorial and Algorithmic Aspects of Networking. CAAN 2007. Lecture Notes in Computer Science, vol 4852. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77294-1_11

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp