An Efficient Distributed Algorithm For st-numbering the Vertices of a Biconnected Graph

Простая страница элемента
dc.creatorAranha,R. F. M.
dc.creatorRangan,C.
dc.date1995
dc.date.accessioned2024-02-06T12:47:54Z
dc.date.available2024-02-06T12:47:54Z
dc.descriptionGiven a biconnected network G with n nodes and a specific edge (r, s) of G, the st-numbering problem asks for an assignment of integers to the nodes satisfying the following condition: r is assigned the number 1 and s is assigned the number n and all other nodes are assigned numbers in such a way that every node (other than r and s) has a neighbour with smaller st-number and a neighbour with larger st-number. Since st-numbering exists iff G is biconnected, it serves as a powerful "local characterization" of the "global" property of the network. We present an efficient O(e) message complexity and O(n) time complexity algorithm for st-numbering a biconnected graph.
dc.formattext/html
dc.identifierhttps://doi.org/10.3217/jucs-001-09-0633
dc.identifierhttps://lib.jucs.org/article/27158/
dc.identifier.urihttps://openrepository.mephi.ru/handle/123456789/6850
dc.languageen
dc.publisherJournal of Universal Computer Science
dc.relationinfo:eu-repo/semantics/altIdentifier/eissn/0948-6968
dc.relationinfo:eu-repo/semantics/altIdentifier/pissn/0948-695X
dc.rightsinfo:eu-repo/semantics/openAccess
dc.rightsJ.UCS License
dc.sourceJUCS - Journal of Universal Computer Science 1(9): 633-651
dc.subjectDistributed graph algorithms
dc.subjectst-numbering
dc.subjectbiconnected graph
dc.titleAn Efficient Distributed Algorithm For st-numbering the Vertices of a Biconnected Graph
dc.typeResearch Article
Файлы
Коллекции
Публикации в журналах НИЯУ МИФИ