On an edge ranking problem of trees and graphs (Q803172)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On an edge ranking problem of trees and graphs |
scientific article; zbMATH DE number 4200257
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On an edge ranking problem of trees and graphs |
scientific article; zbMATH DE number 4200257 |
Statements
On an edge ranking problem of trees and graphs (English)
0 references
1991
0 references
After having introduced the concepts k-edge ranking, k-node ranking, edge rank number and node rank number, \(k\in {\mathbb{N}}\), the authors prove some of their properties, develop an O(n log n) time approximation algorithm for edge ranking of trees and conclude by mentioning that it is an open question whether one can design a polynomial-time algorithm for optimal edge ranking trees.
0 references
k-edge ranking
0 references
k-node ranking
0 references
edge rank number
0 references
node rank number
0 references
0.9371230602264404
0 references
0.884239673614502
0 references
