• DocumentCode
    2406455
  • Title

    Hamiltonian problems for reducible flowgraphs

  • Author

    Vernet, Oswaldo ; Markenzon, Lilian

  • Author_Institution
    Nucl. de Comput. Eletronica, Univ. Fed. do Rio de Janeiro, Brazil
  • fYear
    1997
  • fDate
    10-15 Nov 1997
  • Firstpage
    264
  • Lastpage
    267
  • Abstract
    We discuss Hamiltonian problems for reducible flowgraphs. The main result is finding, in linear time, the unique Hamiltonian cycle, if it exists. In order to obtain this result, two other related problems are solved: finding the Hamiltonian path starting at the source vertex and finding the Hamiltonian cycle given the Hamiltonian path
  • Keywords
    computational complexity; flow graphs; program testing; Hamiltonian cycle; Hamiltonian path; Hamiltonian problems; reducible flowgraphs; source vertex; unique Hamiltonian cycle; Constraint theory; Heuristic algorithms; IEL; NP-complete problem; Testing;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computer Science Society, 1997. Proceedings., XVII International Conference of the Chilean
  • Conference_Location
    Valparaiso
  • Print_ISBN
    0-8186-8052-0
  • Type

    conf

  • DOI
    10.1109/SCCC.1997.637099
  • Filename
    637099
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2406455