File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Optimal edge ranking of trees in linear time

TitleOptimal edge ranking of trees in linear time
Authors
Lam, TWYue, FL
KeywordsGraph Algorithms
Optimal Edge Ranking
Optimal Node Ranking
Time Complexity
Issue Date2001
PublisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm
Citation
Algorithmica (New York), 2001, v. 30 n. 1, p. 12-33 How to Cite?
AbstractGiven a tree, finding an optimal node ranking and finding an optimal edge ranking 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 requires more than quadratic time. In this paper we present a new approach for finding an optimal edge ranking of a tree, improving the time complexity to linear.
Persistent Identifierhttp://hdl.handle.net/10722/152303
ISSN
0178-4617
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 0.905
ISI Accession Number ID
WOS:000167322600002
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorLam, TWen_US
dc.contributor.authorYue, FLen_US
dc.date.accessioned2012-06-26T06:37:02Z-
dc.date.available2012-06-26T06:37:02Z-
dc.date.issued2001en_US
dc.identifier.citationAlgorithmica (New York), 2001, v. 30 n. 1, p. 12-33en_US
dc.identifier.issn0178-4617en_US
dc.identifier.urihttp://hdl.handle.net/10722/152303-
dc.description.abstractGiven a tree, finding an optimal node ranking and finding an optimal edge ranking 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 requires more than quadratic time. In this paper we present a new approach for finding an optimal edge ranking of a tree, improving the time complexity to linear.en_US
dc.languageengen_US
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htmen_US
dc.relation.ispartofAlgorithmica (New York)en_US
dc.subjectGraph Algorithmsen_US
dc.subjectOptimal Edge Rankingen_US
dc.subjectOptimal Node Rankingen_US
dc.subjectTime Complexityen_US
dc.titleOptimal edge ranking of trees in linear timeen_US
dc.typeArticleen_US
dc.identifier.emailLam, TW:twlam@cs.hku.hken_US
dc.identifier.authorityLam, TW=rp00135en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.scopuseid_2-s2.0-0242333202en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0242333202&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume30en_US
dc.identifier.issue1en_US
dc.identifier.spage12en_US
dc.identifier.epage33en_US
dc.identifier.isiWOS:000167322600002-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridLam, TW=7202523165en_US
dc.identifier.scopusauthoridYue, FL=7004029949en_US
dc.identifier.issnl0178-4617-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats