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
KeywordsMathematics computers
Issue Date1998
PublisherSociety for Industrial and Applied Mathematics.
Citation
Proceedings Of The 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

 

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.citationProceedings Of The 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 Annual ACM-SIAM Symposium on Discrete Algorithmsen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectMathematics computersen_HK
dc.titleOptimal edge ranking of trees in linear timeen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1071-9040&volume=&spage=436&epage=445&date=1998&atitle=Optimal+edge+ranking+of+trees+in+linear+timeen_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

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats