File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Optimal edge ranking of trees in linear time

TitleOptimal edge ranking of trees in linear time
Authors
Lam, Tak WahYue, Fung Ling
KeywordsMathematics computers
Issue Date1998
PublisherSociety for Industrial and Applied Mathematics.
Citation
the 9th Annual ACM SIAM Symposium on Discrete Algorithms (SODA 1998), San Francisco, CA, 25-27 January 1998. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998, p. 436-445 How to Cite?
AbstractFinding an optimal node ranking and an edge ranking of a tree are interesting computational problems. The former problem already has a linear time algorithm in the literature. For the latter, only recently polynomial time algorithms have been revealed, and the best known algorithm takes O(n2 log n) time. In this paper, we present a new approach for finding an optimal edge ranking in O(n) time, showing that the optimal edge ranking problem is no more difficult than the node counterpart.
Persistent Identifierhttp://hdl.handle.net/10722/45608
ISSN
1071-9040

 

DC FieldValueLanguage
dc.contributor.authorLam, Tak Wahen_HK
dc.contributor.authorYue, Fung Lingen_HK
dc.date.accessioned2007-10-30T06:30:11Z-
dc.date.available2007-10-30T06:30:11Z-
dc.date.issued1998en_HK
dc.identifier.citationthe 9th Annual ACM SIAM Symposium on Discrete Algorithms (SODA 1998), San Francisco, CA, 25-27 January 1998. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998, p. 436-445en_HK
dc.identifier.issn1071-9040en_HK
dc.identifier.urihttp://hdl.handle.net/10722/45608-
dc.description.abstractFinding an optimal node ranking and an edge ranking of a tree are interesting computational problems. The former problem already has a linear time algorithm in the literature. For the latter, only recently polynomial time algorithms have been revealed, and the best known algorithm takes O(n2 log n) time. In this paper, we present a new approach for finding an optimal edge ranking in O(n) time, showing that the optimal edge ranking problem is no more difficult than the node counterpart.en_HK
dc.format.extent1101298 bytes-
dc.format.extent4181 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypetext/plain-
dc.languageengen_HK
dc.publisherSociety for Industrial and Applied Mathematics.en_HK
dc.relation.ispartofProceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithmsen_HK
dc.rights© 1998 Society for Industrial and Applied Mathematics. First Published in Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms in 1998, published by the Society for Industrial and Applied Mathematics (SIAM).-
dc.subjectMathematics computersen_HK
dc.titleOptimal edge ranking of trees in linear timeen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailLam, Tak Wah:twlam@cs.hku.hken_HK
dc.identifier.authorityLam, Tak Wah=rp00135en_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.scopuseid_2-s2.0-0032272930en_HK
dc.identifier.hkuros42203-
dc.identifier.spage436en_HK
dc.identifier.epage445en_HK
dc.identifier.scopusauthoridLam, Tak Wah=7202523165en_HK
dc.identifier.scopusauthoridYue, Fung Ling=7004029949en_HK
dc.identifier.issnl1071-9040-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats