• DocumentCode
    2178521
  • Title

    A space efficient method for the lowest common ancestor problem and an application to finding negative cycles

  • Author

    Maier, David

  • fYear
    1977
  • fDate
    Oct. 31 1977-Nov. 2 1977
  • Firstpage
    132
  • Lastpage
    141
  • Abstract
    We present a method for computing ancestor information in trees. We show the method is tunable to specific applications, and compare it to other methods. Finally, we apply our procedures to the problem of finding negative cycles in sparse graphs.
  • Keywords
    Performance evaluation; Testing; Tree graphs;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1977., 18th Annual Symposium on
  • Conference_Location
    Providence, RI, USA
  • ISSN
    0272-5428
  • Type

    conf

  • DOI
    10.1109/SFCS.1977.4
  • Filename
    4567935
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2178521