• DocumentCode
    3014311
  • Title

    Container problem in substring reversal graphs

  • Author

    Suzuki, Yasuto ; Kaneko, Keiichi ; Nakamori, Mario

  • Author_Institution
    Dept. of Comput., Inf. & Commun. Sci., Tokyo Univ. of Agric. & Technol., Japan
  • fYear
    2004
  • fDate
    10-12 May 2004
  • Firstpage
    563
  • Lastpage
    568
  • Abstract
    In this paper, we propose an algorithm that solves the container problem in n-substring reversal graphs in polynomial order time of n. Its correctness is proved and estimates of time complexity and sum of path lengths are given. We also report the results of computer experiment conducted to measure the average performance of our algorithm.
  • Keywords
    computational complexity; graph theory; multiprocessor interconnection networks; network topology; program verification; algorithm correctness proving; container problem; path lengths; substring reversal graphs; time complexity; Concurrent computing; Containers; Distributed computing; Fault diagnosis; Hypercubes; Network topology; Parallel architectures; Parallel machines; Polynomials; Routing;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Parallel Architectures, Algorithms and Networks, 2004. Proceedings. 7th International Symposium on
  • ISSN
    1087-4089
  • Print_ISBN
    0-7695-2135-5
  • Type

    conf

  • DOI
    10.1109/ISPAN.2004.1300538
  • Filename
    1300538
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3014311