An Efficient On-Line Algorithm for Edge-Ranking of Trees
| Autor: | Rahman, Muntasir Raihan, Kashem, Abul, Haque, MD. Ehtesamul |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2008 |
| Předmět: | |
| Zdroj: | INFOCOMP Journal of Computer Science; Vol. 7 No. 2 (2008): June, 2008; 21-25 INFOCOMP: Jornal de Ciência da Computação Universidade Federal de Lavras (UFLA) instacron:UFLA |
| ISSN: | 1982-3363 1807-4545 |
| Popis: | An edge-ranking of a graph G is a labeling of the edges of G with positive integers such that every path between two edges with the same label ° contains an edge with label ¸ > °. In the on-line edge-ranking model the edges e1; e2 : : : ; em arrive one at a time in any order, where m is the number of edges in the graph. Only the partial information in the induced subgraph G[fe1; e2; ... ; eig] is available when the algorithm must choose a rank for ei. In this paper, we present an on-line algorithm for ranking the edges of a tree in time O(n2), where n is the number of vertices in the tree. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|